http://acm.hdu.edu.cn/showproblem.php?pid=4059 题意：
给出n，n<=1e8
求1到n里，所有与n互质的数的四次方和
在这里直接考虑，1+....n^4 减去 所有与n不互质的数的4次方
首先我们分解n的质因子，不会很多个
根据容斥原理，
我们枚举 质因子集合S,
那么得到k=n/s,为s的倍数的个数，
而这部分数的四次方和的贡献显然是 k^4（1+2^4+3^4+......x^4）
然后容斥一下就好了，关键是推公式...233智商低 不会推，暴力拉格朗日插一下，
插出1+...n^4= （6*n^5+15n^4+3n^10）/30
求一下30的逆元就可以o1算出答案了。
#include<bits/stdc++.h> using namespace std; long long p[15]; int tot; long long n; const long long mod=1e9+7; const long long mm=233333335; long long get4(long long x) { long long tmp=x*x % mod; return tmp * tmp % mod; } long long f(long long x) { long long sum=0; long long tmp3=x * x % mod * x % mod; sum=(sum+tmp3*10) %mod;; long long tmp4=tmp3*x % mod; sum=(sum+tmp4*15 % mod) % mod; long long tmp5=tmp4*x % mod; sum=(sum+tmp5*6 % mod) % mod; sum=(sum-x+mod)% mod; long long ans=sum * mm % mod; return ans; } int main() { //freopen("in.txt","r",stdin); //freopen("output.txt","w",stdout); int tt; scanf("%d",&tt); while (tt--) { scanf("%lld",&n); long long nn=n; tot=0; for (long long i=2; i*i<=n; i++) { if (nn % i==0) { while (nn % i==0) nn/=i; p[tot++]=i; } } if (nn>1) p[tot++]=nn; /*for (int i=0; i<tot; i++) printf("%d ",p[i]);*/ long long ans=0; for (int state=1; state<(1<<tot); state++) { int num=0; long long pp=1; for (int i=0; i<tot; i++) if (state & (1<<i)) { num++; pp*=p[i]; } long long k=n/pp; long long tmp=get4(pp)*f(k) % mod; if (num % 2) ans+=tmp; else ans-=tmp; ans=ans % mod; } ans=f(n)-ans; ans=(ans+mod)%mod; printf("%lld\n",ans); } return 0; }
