[日常摸鱼]UVA11424&11426 GCD

话说UVa的机子跑的好快呀…

（两题题意一样，前一题数据范围比较小）

题意：求$\sum_{i=1}^{n-1} \sum_{j=i+1}^n gcd(i,j),n<4\times 10^6$

转换一下变成$\sum_{i=2}^{n} \sum_{j=1}^{i-1} gcd(i,j)$，这个形式我们可以设$f(n)=\sum_{i=1}^{n-1} gcd(i,n)$原答案$ans(n)=\sum_{i=2}^{n}f(i)$

考虑如何快速求$f(n)$，根据约数进行分类，对于$n$的一个约数$i$，容易发cai现dao出现的次数是$\phi(\frac{n}{i})$（后来才知道是因为$gcd(x,n)=i$等价于$gcd( \frac{x}{i}, \frac{n}{i})=1$，然后这样的$x$的个数就是$\phi(\frac{n}{i})$了）

经验告诉我们应该预处理出$f(n)$然后递推出所有答案，同样对于$f(n)$我们也得预处理，如果直接对于每个$n$求出约数来统计答案是不太可行的…然后就反过来枚举约数来不断更新$f(n)$

时间复杂度大概是$O(nlogn)$

#include<cstdio>

#include<cstring>

#include<algorithm>

const int N= 4000005;

typedef long long lint;

lint n,tot;

lint pri[N],phi[N],f[N],ans[N];

bool p[N];

inline void init()

{

    phi[1]=1;

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

    {

        if(!p[i])

        {

            pri[++tot]=i;

            phi[i]=i-1;

        }

        for(register int j=1;j<=tot&&i*pri[j]<N;j++)

        {

            p[i*pri[j]]=1;

            if(i%pri[j]==0){phi[i*pri[j]]=phi[i]*pri[j];break;}

            else phi[i*pri[j]]=phi[i]*(pri[j]-1);

        }

    }

}

int main()

{

    init();

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

        for(register int j=i*2;j<N;j+=i)f[j]+=i*phi[j/i];

    for(register int i=1;i<N;i++)ans[i]=ans[i-1]+f[i];

    while(scanf("%lld",&n)==1&&n)

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

    return 0;

}

本地预处理跑了5s…然后交到UVa上居然快的飞起…

巴特西

[日常摸鱼]UVA11424&11426 GCD - Extreme

最新文章

热门文章