将与N不互质的数全部找出来，再应用容斥定理求得最后的结果。这题在求 a/b MOD c 的时候使用费马小定理等价于 a*b^c(-2) MOD c.用x/lnx 可以估计出大概有多少素数。
代码如下：
#include#include #include #include #include #define MOD 1000000007LLusing namespace std;typedef long long int Int64;typedef long long int LL;Int64 rec[55000000], res;int idx;Int64 N, sum;Int64 _pow(Int64 a, Int64 b){ a %= MOD; Int64 ret = 1; while (b) { if (b & 1) { ret *= a; ret %= MOD; } a *= a; a %= MOD; b >>= 1; } return ret;}void PowMode( ){ res = 1; LL a = 30LL; LL b = MOD - 2; while( b ) { if( b&1 ) res = (res*a)%MOD; a = ( a * a )%MOD; b >>= 1; }}Int64 Get_sum( Int64 N ){ Int64 ans = N; ans = ( ans * ( N + 1 ) )%MOD; ans = ( ans * ( 2 *N + 1 ) )%MOD; ans = ( ans * ( ( 3 * N * N )%MOD + (3*N)%MOD - 1 + MOD)%MOD )%MOD; return (ans * res)%MOD;}void cut(Int64 x){ idx = 0; int LIM = (int)sqrt(double(x)); if (!(x & 1)) { rec[++idx] = 2; while (!(x & 1)) { x /= 2; } } for (int i = 3; i <= LIM; i += 2) { if (x % i == 0) { rec[++idx] = i; while (x % i == 0) { x /= i; } } } if (x != 1) { rec[++idx] = x; }}void dfs(int p, Int64 num, int sign){ if (p == idx) { if (num > 1) { sum += sign * (_pow(num, 4) * Get_sum(N/num)) % MOD; sum = ((sum % MOD) + MOD) % MOD; } return; } dfs(p+1, num, sign); dfs(p+1, num*rec[p+1], -sign);}int main(){ int T; PowMode(); scanf("%d", &T); while (T--) { sum = 0; scanf("%I64d", &N); cut(N); dfs(0, 1, -1); printf("%I64d\n", (((Get_sum(N)-sum) % MOD) + MOD) % MOD); } return 0;}