链接 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(...