UVA - 11426 欧拉函数（欧拉函数表）

题意：

给一个数 N ，求 N 范围内所有任意两个数的最大公约数的和。

思路：

f 数组存的是第 n 项的 1~n-1 与 n 的gcd的和，sum数组存的是 f 数组的前缀和。

sum[n]=f[1]+f[2]+f[3]+…+f[n]

sum[n-1]=f[1]+f[2]+…+f[n-1]

sum[n]=sum[n-1]+f[n]

所以我们求出f[n]的值即可

1~n-1与 n 的最大公约数暴力来求肯定超时；

设gcd(x,n)=i 表示 n 和 x 的最大公约数为i，那么gcd( x/i , n/i )=1

即转化为求n/i 的欧拉函数值。a[ n / i ]

比如:

a [ 6 / 1 ] = a[ 6 ] = 2

a[ 6 / 2 ] = a[ 3 ] = 2

a[ 6 / 3 ] = a[ 2 ] = 1

a[ 6 / 4 ] = a[ 1 ] = 1

a[ 6 / 5 ] = a[ 1 ] = 1

a [ j / i ] * i =2 * 1+2 * 2 + 1 * 3

    for(int i=1;i<N;i++)//计算1~N的所有数

        for(int j=i*2;j<N;j=j+i)// [1,n-1] 与n的gcd 的和

        //j必须是i的整数倍 ，因为下面要计算 j/i

            f[j]+=a[j/i]*i;

欧拉函数数组 a[ n ] 装的是 n 以内与 n互质的数。

欧拉函数表：

    a[1]=1;

    for(int i=2;i<N;i++)//欧拉函数表

    {

        if(!a[i])//素数筛的基础，i 进去的是素数

            for(int j=i;j<N;j=j+i)

            {

                if(!a[j]) a[j]=j;

                a[j]=a[j]/i*(i-1);//欧拉公式  φ（n）=n * (1 - 1/p1)  * （1 - 1/p2）* .....

            }

    }

完整代码：

#include<string.h>

#include<stdio.h>

#define N 4000010

typedef long long ll;

ll f[N+5],ans[N+5],a[N+5];

void yao()

{

    for(int i=0;i<=N;i++)

        f[i]=0,ans[i]=0,a[i]=0;

    a[1]=1;

    for(int i=2;i<N;i++)//欧拉打表

    {

        if(!a[i])

            for(int j=i;j<N;j=j+i)

            {

                if(!a[j]) a[j]=j;

                a[j]=a[j]/i*(i-1);

            }

    }

    for(int i=1;i<N;i++)

        for(int j=i*2;j<N;j=j+i)//[1,n-1] 与n的gcd 的和

            f[j]+=a[j/i]*i;

// f[6]=a[6/1==1]*1 + a[6/2==3]*2 + a[6/3==2]*3

//////    for(int i=1;i<=6;i++)

//////        printf("%d ",a[i]);

//////    printf("\n");

    for(int i=2;i<=N;i++)

        ans[i]=ans[i-1]+f[i];

}

int main()

{

    int n;

    yao();

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

        printf("%lld\n",ans[n]);

    return 0;

}

/*

f[6]

1,6 5,6  1=a[6]

2,6 4,6  2=a[3]

3,6      1=a[2]

*/

巴特西

UVA - 11426 欧拉函数（欧拉函数表）

最新文章

热门文章