將與N不互質的數全部找出來，再應用容斥定理求得最后的結果。這題在求 a/b MOD c 的時候使用費馬小定理等價于 a*b^c(-2) MOD c.用x/lnx 可以估計出大概有多少素數。

代碼如下：

#include <cstdlib> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #define MOD 1000000007LL using 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; }

轉載于:https://www.cnblogs.com/Lyush/archive/2012/07/28/2613700.html

總結

以上是生活随笔為你收集整理的HDU-4059 The Boss on Mars 容斥定理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。