1349. 最大公约数 (Standard IO)

Time Limits: 1000 ms Memory Limits: 65536 KB

Description

　　小菜的妹妹小诗就要读小学了！正所谓计算机要从娃娃抓起，小菜决定在幼儿园最后一段轻松的时间里教妹妹编程。

　　小菜刚教完gcd即最大公约数以后，一知半解的妹妹写了如下一段代码：

　　 sum:=0;

　　 for i:=1 to n-1 do

　　 for j:=i+1 to n do sum:=sum+gcd(i,j)

　　显然这个程序的效率是很低的，小明打算写一个更强的程序，在求出sum的同时比妹妹跑的更快。

Input

　　第一行一个整数t，即表示有t组数据

　　接下来t行，每行一个整数n

Output

　　t行，每行一个整数，表示n所对应的sum值

Sample Input

2

10

100

Sample Output

67

13015

Data Constraint

Hint

【数据规模】

　　20%数据t≤100,n≤100

　　40%数据t≤1000,n≤2000

　　100%数据t≤10000,n≤1000000

题解

看到了gcd，那就很明显是数论题

对这道题我们要求的是

∑i=1n−1∑j=i+1ngcd(i,j)

固定j，那么

∑i=1ngcd(i,n)

=∑i=1n∑d|n[gcd(i,n)==d]∗d

=∑i=1n∑d|n[gcd(id,nd)==1]∗d

=∑d|nφ(nd)∗d

因此，答案就是

∑i=2n∑j=1⌊n/i⌋φ(i)∗j

用前缀和优化一下

记ans[i∗j]=φ(i)∗j，答案就是

∑i=2nans[i]

代码

#include<cstdio>

#define M 80000

#define N 1000010

#define max(a,b) (((a)>(b))?(a):(b))

long a[N],p[M],phi[N],t;

long long ans[N];

bool b[N];

int main()

{   long tot,n,i,j,k,maxx=0;

    scanf("%ld",&tot);

    for(i=1;i<=tot;i++){

        scanf("%ld",&a[i]);

        maxx=max(maxx,a[i]);

    }

    n=maxx;

    phi[1]=1;

    for(i=2;i<=n;i++){

        if(!b[i]){

            phi[i]=i-1;

            p[++t]=i;

        }

        for(j=1;j<=t&&i*p[j]<=n;j++){

            b[i*p[j]]=true;

            if(i%p[j]==0){

                phi[i*p[j]]=phi[i]*p[j];

                break;

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

        }

    }

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

        for(j=1;j<=n/i;j++)

            ans[i*j]+=phi[i]*j;

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

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

    for(k=1;k<=tot;k++)

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

    return 0;

}

巴特西

JZOJ 1349. 最大公约数 (Standard IO)