Longge's problem poj2480 欧拉函数，gcd

Longge's problem

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 6918		Accepted: 2234

Description

Longge is good at mathematics and he likes to think about hard mathematical problems which will be solved by some graceful algorithms. Now a problem comes: Given an integer N(1 < N < 2^31),you are to calculate ∑gcd(i, N) 1<=i <=N.

"Oh, I know, I know!" Longge shouts! But do you know? Please solve it.

Input

Input contain several test case.
A number N per line.

Output

For each N, output ,∑gcd(i, N) 1<=i <=N, a line

Sample Input

2

6

Sample Output

3

15

Source

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <math.h>

 #include <string.h>

 #define MAXN 100010

 #define INF 0x7fffffff

 using namespace std;

 long long a[]= {},b[],nu,c[][],cn;

 void init()

 {

     nu=;

     long long i,j;

     for(i=; i<; i++)

     {

         if(!a[i])

         {

             b[nu++]=i;

             j=i*i;

             while(j<)

             {

                 a[j]=;

                 j+=i;

             }

         }

     }

 }

 void fun(long long x)

 {

     long long i;

     memset(c,,sizeof(c));

     cn=;

     for(i=; b[nu]<=x&&i<nu; i++)

     {

         if(x%b[i]==)

         {

             c[cn][]=b[i];

             while(x%b[i]==)

             {

                 c[cn][]++;

                 x/=b[i];

             }

             cn++;

         }

     }

     if(x!=)

     {

         c[cn][]=x;

         c[cn++][]=;

     }

 }

 long long so(long long n,long long x)

 {

     long long i=,sum=n;

     while(x)

     {

         if(x&)

         {

             sum=sum/c[i][]*(c[i][]-);

             sum*=c[i][];

         }

         i++;

         x>>=;

     }

     return sum;

 }

 long long work(long long n)

 {

    long long i,size=<<cn,sum=;

    for(i=;i<size;i++)

    {

        sum+=so(n,i);

    }

    return sum;

 }

 int main()

 {

     init();

     long long n;

     while(~scanf("%I64d",&n))

     {

         fun(n);

         printf("%I64d\n",work(n));

     }

 }

设函数g(n) = gcd(i,n) (1<=i<=n)，由积性函数的定义，g(n)=g(m1)*g(m2) (n=m1*m2 且（m1, m2）= 1)，所以g是积性函数。由具体数学上的结论，积性函数的和也是积性的。所以f(n) = ∑gcd(i, n)也是积性函数。由初等数论中的定理，如果f(n)是不恒为0的数论函数，n>1时 n=p1^a1*p2^a2*...*ps^as，那么f(n)是积性函数的充要条件是f(1)=1，及f(n) = f(p1^a1)*f(p2^a2)*...f(pr^ar)。所以只要求f(pi^ai)就好，如果d是n的一个约数，那么1<=i<=n中gcd(i,n) = d的个数是phi(n/d)，即n/d的欧拉函数

f(pi^ai) = Φ（pi^ai）+pi*Φ（pi^(ai-1)）+pi^2*Φ（pi^(ai-2)）+...+pi^(ai-1)* Φ（pi）+ pi^ai *Φ（1）

= pi^(ai-1)*(pi-1) + pi*pi^(ai-2)*(pi-1)....+pi^ai

= pi^ai*(1+ai*(1-1/pi))

f(n) = p1^a1*p2^a2...*pr^ar*(1+a1*(1-1/p1))*(1+a2*(1-1/p2))*...

= n*(1+a1*(1-1/p1))*(1+a2*(1-1/p2))*...

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <math.h>

 #include <string.h>

 #define MAXN 100010

 #define INF 0x7fffffff

 using namespace std;

 int a[]= {},b[],nu,c[][],cn;

 void init()

 {

     nu=;

     long long i,j;

     for(i=; i<; i++)

     {

         if(!a[i])

         {

             b[nu++]=i;

             j=i*i;

             while(j<)

             {

                 a[j]=;

                 j+=i;

             }

         }

     }

 }

 void fun(long long x)

 {

     long long i;

     memset(c,,sizeof(c));

     cn=;

     for(i=; b[nu]<=x&&i<nu; i++)

     {

         if(x%b[i]==)

         {

             c[cn][]=b[i];

             while(x%b[i]==)

             {

                 c[cn][]++;

                 x/=b[i];

             }

             cn++;

         }

     }

     if(x!=)

     {

         c[cn][]=x;

         c[cn++][]=;

     }

 }

 long long work(long long n)

 {

    long long i,sum=n;

    for(i=;i<cn;i++)

    {

        sum=sum+sum*c[i][]*(c[i][]-)/c[i][];

    }

    return sum;

 }

 int main()

 {

     init();

     long long n;

     while(~scanf("%I64d",&n))

     {

         fun(n);

         printf("%I64d\n",work(n));

     }

 }

巴特西

Longge's problem poj2480 欧拉函数，gcd

最新文章

热门文章