题意：求小于\(n\)且与\(n\)互质的数的四次方和。
题解：
四次方求和公式：\(1^4+2^4+...+n^4 = \frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}\)
设初始答案为\(sum(n)=1^4+2^4+..+n^4\)，将\(n\)分解质因数后考虑容斥，枚举每个质因数\(p\)的倍数四次方和，在答案里减掉。再枚举每两个质因数的乘积\(p*q\)的倍数的四次方和，在答案里加上...直到枚举到全部。我们可以单纯枚举每个数选与不选，然后看选择的个数来决定把倍数和加或者减。
现在的问题是，如何快速求\(p\)的倍数次方和呢？考虑\(p\)的倍数次方和为\(p^4+(2p)^4+..+(n/p*p)^4=p^4*(1+2^4+..+(n/p)^4)\)，所以还可以用求和公式\(O(1)\)求出。
复杂度\(O(sqrt(n)*2^{log(n)})\)。理论上不行，实际数据跑的飞快。
代码：
#include <bits/stdc++.h>
#define fopi freopen("in.txt", "r", stdin)
#define fopo freopen("out.txt", "w", stdout)
using namespace std;
typedef long long LL;
const int MOD = 1000000007;
const int maxn = 100 + 10;
const int inv30 = 233333335;
vector<int> V;
LL sum(LL n) {
return n * (n+1) % MOD * ((2*n+1) % MOD) % MOD * ((3*n%MOD*n%MOD+3*n-1) % MOD) % MOD * inv30 % MOD;
}
int T, n, tot;
LL ans;
int prime[maxn];
void dfs(int x, LL res, int num) {
if (x > tot) {
if (num == 0) return;
LL tmp = sum(n/res);
for (int i = 1; i <= 4; i++) tmp = tmp * res % MOD;
if (num % 2 == 1) ans = (ans - tmp + MOD) % MOD;
else ans = (ans + tmp) % MOD;
return;
}
dfs(x+1, res * prime[x] % MOD, num+1);
dfs(x+1, res, num);
}
int main() {
scanf("%d", &T);
for (int ca = 1; ca <= T; ca++) {
tot = 0;
scanf("%d", &n);
int tmp = n;
for (int i = 2; i <= sqrt(tmp); i++) {
if (tmp % i == 0) {
prime[++tot] = i;
while(tmp % i == 0) tmp /= i;
}
}
if (tmp != 1) prime[++tot] = tmp;
ans = sum(n);
dfs(1, 1, 0);
printf("%lld\n", ans);
}
}
The Boss on Mars HDU - 4059（数学 + 容斥）
原文：https://www.cnblogs.com/ruthank/p/11385408.html