20190811模拟赛T4 最大公约数 解题报告

根据欧拉函数的定义，令 是 的第 个因数，且满足。 则这样的x
有 个， 两边同乘以 ， 即可推出 。（显然）

以内与 的最大公约数为 的数有个。

与所有小于 的数的最大公约数之和为

for(i=1;i<=n;i++) //枚举n的约数
    if(n%i==0) f[n]+=phi[n/i]*i;

外层还要枚举每个数字，故时间复杂度为

可惜要T。

那么就可以优化一下，枚举那个公因数，累加答案。

见代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define maxn 1000000
using namespace std;
int n;
long long phi[1000001],f[1000001];
void Si()
{
    for(int i=2;i<=maxn;i++) phi[i]=i;
    for(int i=2;i<=maxn;i++)
        if(phi[i]==i)
            for(int j=i;j<=maxn;j+=i) phi[j]=phi[j]/i*(i-1);
}
void PreWork()
{
    for(int i=1;i<=maxn;i++)
        for(int j=2;j<=maxn/i;j++) f[i*j]+=phi[j]*i;
    for(int i=1;i<=maxn;i++) f[i]+=f[i-1];
}
int main()
{
    Si();
    PreWork();
    int t;
    scanf("%d",&t);
    while(t--) scanf("%d",&n),printf("%lld\n",f[n]);
    return 0;
}

预处理， 询问。