首页 > 代码库 > HDU 4059：The Boss on Mars（数学公式+容斥原理）
HDU 4059：The Boss on Mars（数学公式+容斥原理）
http://acm.hdu.edu.cn/showproblem.php?pid=4059
题意：给出一个n，求1~n里面与n互质的数的四次方的和是多少。
思路；不知道1~n的每个数的四次方的求和公式。看的是这篇：http://blog.csdn.net/acm_cxlove/article/details/7434864。
求和公式：(1^4+2^4+……+n^4)=(n*(n+1)*(2n+1)*(3*n*n+3*n-1))/30;
然后先求出1~n的每个数的四次方的求和，然后再减去n的因子的四次方的求和。
把n的因子的质因子找出来，然后使用容斥原理去做。
容斥原理里面有一个点：例如要求所有2的倍数的因子，n是8的话，就有因子2，4，6，8，求这些的四次方的和就可以转化为2 ^ 4 * (1 ^ 4 + 2 ^ 4 + 3 ^ 4 + 4 ^ 4)。就是f_pow(prime[i], 4) * calsum(n / prime[i])。
除以30就是乘以30的逆元，就是f_pow(30, MOD-2);
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int MOD = 1e9 + 7; 5 const int N = 1e5 + 10; 6 // (1^4+2^4+……+n^4)=(n*(n+1)*(2n+1)*(3*n*n+3*n-1))/30; 7 LL inver, n; 8 int prime[N], not_prime[N], cnt; 9 vector<LL> fac;10 11 void Biao() {12 cnt = 0;13 for(int i = 2; i <= N; i++) {14 if(not_prime[i]) continue;15 prime[cnt++] = i;16 for(int j = 2 * i; j <= N; j += i) not_prime[j] = 1;17 }18 }19 20 LL f_pow(LL a, LL b) {21 LL ans = 1;22 a %= MOD, b %= MOD;23 while(b) {24 if(b & 1) ans = ans * a % MOD;25 a = a * a % MOD;26 b >>= 1;27 }28 return ans % MOD;29 }30 31 LL calsum(LL n) {32 LL ans = n;33 ans = ans * ((n + 1) % MOD) % MOD;34 ans = ans * ((2 * n + 1) % MOD) % MOD;35 ans = ans * (((3 * n * n % MOD) + (3 * n % MOD) - 1 + MOD) % MOD) % MOD;36 ans = ans * inver % MOD;37 return ans;38 }39 40 void solve() {41 fac.clear();42 LL tmp = n;43 for(int i = 0; i < cnt; i++) {44 if(tmp % prime[i] == 0) {45 fac.push_back(prime[i]);46 while(tmp % prime[i] == 0) tmp /= prime[i];47 }48 }49 if(tmp > 1) fac.push_back(tmp);50 LL ans = calsum(n);51 int sz = fac.size();52 for(int st = 1; st < (1 << sz); st++) {53 int num = 0, bit = 0; LL now = 1;54 while((1 << bit) <= st) {55 if(st & (1 << bit)) num++, now *= fac[bit];56 bit++;57 }58 LL res = f_pow(now, 4LL) * (calsum(n / now) % MOD) % MOD;59 if(num % 2) ans = (ans - res + MOD) % MOD;60 else ans = (ans + res + MOD) % MOD;61 }62 printf("%lld\n", ans);63 }64 65 int main() {66 inver = f_pow(30LL, MOD - 2);67 // printf("%lld\n", inver);68 Biao();69 int t; scanf("%d", &t);70 while(t--) {71 scanf("%lld", &n);72 solve();73 }74 return 0;75 }
HDU 4059：The Boss on Mars（数学公式+容斥原理）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。