codeforces100917 Constant Ratio

逃离我推掉我的手 2022-07-16 03:39 141阅读 0赞

codeforces100917 Constant Ratio 题目链接：[http://codeforces.com/gym/100917/problem/C][http_codeforces.com_gym_100917_problem_C]

题面描述：

C. Constant Ratio

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Given an integer *n*, find out number of ways to represent it as the sum of two or more integers *a**i* with the next property: ratio *a**i* / *a**i* - 1 is the same positive integer for all possible *i* > 1.

Input

Input consists of one integer *n* (1 ≤ *n* ≤ 105).

Output

Print one integer — number of representations.

Examples

input

output

input

output

input

567

output

Note

In the first sample no such representation exists.

In the second sample there exist two representations:

*  1 1 1 1 1, then *q* = 1.
 *  1 4, then *q* = 4.

题目大意：

求等比数列的前n项和，看前n项和能否得到n。

题目分析：

可以先找出每一个可以被n整除的数，作为a1，然后再找公比，由于是等比数列，所以时间复杂度不是很高。

代码实现：方法一：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cstdlib>
    #include <cmath>
    
    using namespace std;
    typedef long long LL;
    int n;
    
    bool find(int a1,int a2)
    {
        int k=a2/a1;
        LL ak=a1;
        LL sum=a1;
        while(1)
        {
            ak*=k;
            sum+=ak;
            if (sum==n) return true;
            if (sum>n) return false;
        }
    }
    
    int main()
    {
        while(scanf("%d",&n)!=-1)
        {
            int ans=0;
            for(int i=1; i<n; i++) if (n%i==0)
            {
                for(int j=i; j<=n; j+=i)
                {
                    if (find(i,j)) ans++;
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

方法二：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <cmath>
    
    using namespace std;
    
    long long n;
    long long pow(long long a,long long q)
    {
        long long ans=1;
        while(q--)
            ans*=a;
        return ans;
    }
    bool find(long long a1,long long a2)
    {
        long long q=a2/a1;
        if(q==1)
        {
            if(n%a1==0)
                return true;
            else
                return false;
        }
        for(long long k=1; k<=n*n; k++)///注意k的范围给的给定,要使得能够跳出循环
        {
            if(n==(a1*(pow(q,k)-1)/((q-1))))
                return true;
            else if((a1*(pow(q,k)-1)/((q-1)))>n)
                return false;
            else continue;
    
        }
    }
    
    int main()
    {
        while(scanf("%lld",&n)!=-1)
        {
            if(n==1)
                printf("0\n");
            else
            {
                long long ans=0;
                for(long long i=1; i<n; i++)//a1,不带n
                {
                    if(n%i==0)
                    {
                        for(long long j=i; j<=n; j+=i)
                        {
                            if(find(i,j)) ans++;
                        }
                    }
                }
                printf("%lld\n",ans);
            }
        }
        return 0;
    }

[http_codeforces.com_gym_100917_problem_C]: http://codeforces.com/gym/100917/problem/C