The Boss on Mars

思路

顯然我們可以求得${\sum }_{i=1}^n{i}^4=\frac{6n^5+15n^4+10n^3?n}{30}$，接下來就是考慮把其中不與$n$互質的數給踢出去了，顯然我們可以考慮容斥。

假設$n=p_1^{a_1}{p}_2^{a_2}{p}_3^{a_3}\dots p_{n?1}^{a_{n?1}}{p}_n{a}_n$

假設給定一個數字$x=p_1^{k_1}{p}_2^{k_2}{p}_3^{k_3}\dots p_{n?1}^{k_{n?1}}{p}_n^{k_n}$我們找出$n$中是$x$的倍數的數字來，

可以寫成$sum=x^4(1^4+2^4+3^4+?+(\frac{n}{x}?1{)}^4+(\frac{n}{x}{)}^4)$，

然后再按照容斥的原則奇加，偶減，當有奇數個因子的時候加上$sum$，有偶數個因子的時候減去$sum$。

代碼

/*Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h>using namespace std;typedef long long ll;const int inf = 0x3f3f3f3f;const int N = 1e4 + 10, mod = 1e9 + 7;int prime[N], cnt;bool st[N];int fac[30], tot, m;void init() {for(int i = 2; i < N; i++) {if(!st[i]) prime[cnt++] = i;for(int j = 0; j < cnt && i * prime[j] < N; j++) {st[i * prime[j]] = 1;if(i % prime[j] == 0) break;}} }ll calc1(ll n) {ll ans = ans = (1ll * 6 * n % mod * n % mod * n % mod * n % mod * n % mod + 1ll * 15 * n % mod * n % mod * n % mod * n % mod + 1ll * 10 * n % mod * n % mod * n % mod - n + mod) % mod;ans = ans * 233333335 % mod;return ans; }ll calc2() {ll ans = 0;for(int i = 1; i < (1 << tot); i++) {int sum = 0, now = 1;for(int j = 0; j < tot; j++) {if(i >> j & 1) {now *= fac[j];sum++;}}if(sum & 1) ans = (ans + calc1(m / now) * now % mod * now % mod * now % mod * now % mod) % mod;else ans = (ans - calc1(m / now) * now % mod * now % mod * now % mod * now % mod + mod) % mod;}return ans; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int T; cin >> T;init();while(T--) {int n;cin >> n;m = n;tot = 0;for(int i = 0; prime[i] * prime[i] <= n; i++) {if(n % prime[i] == 0) {fac[tot++] = prime[i];while(n % prime[i] == 0) {n /= prime[i];}}}if(n != 1) fac[tot++] = n;ll ans1 = calc1(m);ll ans2 = calc2();cout << (ans1 - ans2 - (m == 1) + mod) % mod << endl;}return 0; }

總結

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

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