链接 GCD 思路 显然,除了素数的整数次幂,其余的数的 值均为 。对于一个素数 ,则有 。于是可以考虑在线性筛素数的过程中预处理出 ,这很好预处理,线性筛中记录下每个数 的最小质因数 ,然后对有大于一个质因子的数打上标记。时间复杂度为 。 代码 #include<bits/stdc++.h> #define MAXN 10000010 #define ll long long using namespace std; ll v[MAXN],prime[MAXN],m=0,f[MAXN],s[MAXN]; bool vh[MAXN]; void primes(...