hdu4059 容斥原理

傳送門

題意：求小于n的與n互素的數的四次方的和對1e9+7取模。

思路：我們還是考慮一下逆問題，求小于n的與n不互素的數的四次方和，是以還是枚舉n的素因子，再用容斥原理，這裡需要一個公式就是1+2^4+3^4+...+n^4，百度一下就可以得到，簡單推導一下，利用了累加法，考慮了比四次方高一次的五次來求

(n+1)^5-n^5=1+5n+10n^2+10n^3+5n^4，那麼：

 n^5-(n-1)^5=1+5(n-1)+10(n-1)^2+10(n-1)^3+5(n-1)^4，

...

...

      2^5-1^5=1+5*1+10*1+10+1+5+1

累加，則左邊=(n+1)^5-1=n+5(n+(n-1)+...+1)+10(n^2+(n-1)^2+...+1)+10(n^3+(n-1)^3+...+1)+5(n^4+(n-1)^4+...+1)=右邊

其中n^3+(n-1)^3+...+1也用類似的方法，這就可以得到n^4+(n-1)^4+...+1了

最後推得n^4+(n-1)^4+...+1=n*(n+1)*(2*n+1)*(3*n^2+3*n-1)/30

還有我們要求小于n的與n互素的數的四次方的和，那麼在枚舉n的素因子組合的時候，如果得到一個素因子組合比如mul，那麼小于n的是mul的倍數的數的四次方的和為(1+2^4+...+(n/mul)^4)*mul^4，這樣就免去循環計算的麻煩

完整代碼：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
vector<int> p;
LL quickmod(LL a,LL b)
{
    a=a%mod;
    LL ans=1;
    while(b)
    {
        if(b&1)
        {
            ans=ans*a%mod;
        }
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
LL getpow(LL n)///1+2^4+3^4+4^4+...+n^4
{
    LL ans=((n*(n+1)%mod)*(2*n+1)%mod)*(3*((n*n)%mod)+3*n-1)%mod;
    ans=ans*quickmod(30LL,mod-2);
    return ans%mod;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        LL n;
        scanf("%lld",&n);
        p.clear();
        int temp=n;
        for(int i=2;i*i<=temp;i++)
        {
            if(temp%i==0)
            {
                p.push_back(i);
                while(temp%i==0)
                {
                    temp/=i;
                }
            }
        }
        if(temp>1) p.push_back(temp);
        LL S=0;
        for(int i=1;i<(1<<p.size());i++)
        {
            LL mul=1;
            LL cnt=0;
            for(int j=0;j<p.size();j++)
            {
                if(i&(1<<j))
                {
                    cnt++;
                    mul=mul*p[j]%mod;
                }
            }
            if(cnt&1)
                S=(S+getpow(n/mul)*quickmod(mul,4)%mod)%mod;
            else
                S=(S-getpow(n/mul)*quickmod(mul,4)%mod)%mod;
        }
        LL ans=getpow(n);
        ans=ans-S;
        ans=(ans%mod+mod)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}