PE 108 Diophantine reciprocals I (数论：分式个数)

古城微笑少年丶 2022-07-13 04:22 125阅读 0赞

[PE108][]  
分式1a\+1b=1n的不同个数其实就是1\+d(n2)2，其中d(n)是n的约数个数。

证明：1b=1n−1a=a−nan

==>b=ana−n

==>an−n(a−n)=n2，所以，gcd(an,a−n) divide n2

==>但是如果 a−n divide an 那么 gcd(an,a−n)=a−n ，那么 a−n divide n2

那么令 a=d\+n,那么 d就是 n2的一个约数。

倒过来说，如果 d 是n2的一个约数，那么令 a=d\+n

那么，b=ana−n=n(n\+d)d=n\+n2d

因为 b是一个整数，所以 d divide n2.

又因为1a\+1a=1n，所以，a=2n

所以，1a\+1b=1n的个数就是：d(n2)−12\+1=d(n2)\+12

代码：

#include<bits/stdc++.h>
    using namespace std;
    vector<int> primes;
    int prime[1000000];
    void getPrimes(int prime[] )
    {   
        for(int i = 0 ; i < 1000000 ; i++){
            prime[i] = 1;   
        }
        for(int i = 2 ; i < 1000000; i++)
        {
            if (prime[i])
            {
                primes.push_back(i);
                if(i <= (int)sqrt((double)1000000))
                {    
                    for(int t = i*i ; t<1000000 ; t+=i)//prime[i*i+k*i]=false
                    {   
                        prime[t] = 0;
                    }
                }
            }
        }
    }
    int divisors_Of_Squared(int n,int prime[] ) // 
    {
        int p, e, i = 0, m = n, result = 1;
        while ( m > 1 )
        {
            e = 1;
            p = primes[i];
            while ( m % p == 0 )
            {
                e += 2;
                m /= p;
            }
            i++;
            result *= e;
        }
        //cout<<result<<endl;
        return result;
    }
    
    int factors(int n)
    {
            int i = 2, k = 0, m = n, count = 1;
            while(m > 1)
            {
                for(; i <= m; i ++)
                     if(m % i == 0)
                        {
                            k = 1;
                            while(m % i == 0)
                            {
                                    k +=2; //k+=2就变成 n^2 的约数个数，k++；就是 n 的约数个数 
                                    m /= i;
                            }
                            count *= k;
                        }
            }
            return count;
    }
    
    int main()
    {
        cout<<factors(2)<<endl;
        int n, s;
        getPrimes(prime);
    
        for (n = 1; ; n ++ )
        {
            // s = (divisors_Of_Squared(n,prime) + 1 ) / 2;  //快 
            s=(factors(n)+1)/2;  //慢 
            if(s>1000)
            {
                break;
            }
    
        }
        cout<<"ans="<<n<<endl;
        return 0;
    }

[PE108]: https://projecteuler.net/problem=108