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);

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 const int MOD = 1e9 + ;

 const int N = 1e5 + ;

 // (1^4+2^4+……+n^4)=(n*(n+1)*(2n+1)*(3*n*n+3*n-1))/30;

 LL inver, n;

 int prime[N], not_prime[N], cnt;

 vector<LL> fac;

 void Biao() {

     cnt = ;

     for(int i = ; i <= N; i++) {

         if(not_prime[i]) continue;

         prime[cnt++] = i;

         for(int j =  * i; j <= N; j += i) not_prime[j] = ;

     }

 }

 LL f_pow(LL a, LL b) {

     LL ans = ;

     a %= MOD, b %= MOD;

     while(b) {

         if(b & ) ans = ans * a % MOD;

         a = a * a % MOD;

         b >>= ;

     }

     return ans % MOD;

 }

 LL calsum(LL n) {

     LL ans = n;

     ans = ans * ((n + ) % MOD) % MOD;

     ans = ans * (( * n + ) % MOD) % MOD;

     ans = ans * ((( * n * n % MOD) + ( * n % MOD) -  + MOD) % MOD) % MOD;

     ans = ans * inver % MOD;

     return ans;

 }

 void solve() {

     fac.clear();

     LL tmp = n;

     for(int i = ; i < cnt; i++) {

         if(tmp % prime[i] == ) {

             fac.push_back(prime[i]);

             while(tmp % prime[i] == ) tmp /= prime[i];

         }

     }

     if(tmp > ) fac.push_back(tmp);

     LL ans = calsum(n);

     int sz = fac.size();

     for(int st = ; st < ( << sz); st++) {

         int num = , bit = ; LL now = ;

         while(( << bit) <= st) {

             if(st & ( << bit)) num++, now *= fac[bit];

             bit++;

         }

         LL res = f_pow(now, 4LL) * (calsum(n / now) % MOD) % MOD;

         if(num % ) ans = (ans - res + MOD) % MOD;

         else ans = (ans + res + MOD) % MOD;

     }

     printf("%lld\n", ans);

 }

 int main() {

     inver = f_pow(30LL, MOD - );

 //    printf("%lld\n", inver);

     Biao();

     int t; scanf("%d", &t);

     while(t--) {

         scanf("%lld", &n);

         solve();

     }

     return ;

 }

巴特西

HDU 4059：The Boss on Mars（数学公式+容斥原理）

最新文章

热门文章