The Boss on Mars HDU

The Boss on Mars (HDU - 4059)

题意：求小于(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
", ans);
    }
}