http://acm.hdu.edu.cn/showproblem.php?pid=4059
题意很好理解,熔池原理,还有公式 http://math2.org/math/expansion/power.htm
#include<cstdio> #include<cstring> #include <iostream> using namespace std; const __int64 iv30 = 233333335; const __int64 mod=1000000007; __int64 n; __int64 cal(__int64 x) { __int64 y=n/x; return (x*x)%mod*x%mod*x%mod*((6*y%mod*y%mod*y%mod*y%mod*y%mod+(15*y%mod*y%mod*y%mod*y)%mod)%mod+10*y%mod*y%mod*y%mod-y)%mod*iv30%mod; } int main() { int ca,p[100]; scanf("%d",&ca); while(ca--) { scanf("%I64d",&n); int cnt=0; __int64 tmp=n; for(int i=2;i*i<=tmp;i++) if(tmp%i==0) { p[cnt++]=i; while(tmp%i==0) tmp/=i; } if(tmp!=1) p[cnt++]=tmp; __int64 ans=0; for(__int64 i=1;i<(1<<cnt);i++) { int num=0; __int64 mul=1; for(__int64 j=0;j<cnt;j++) if(i&(1<<j)) num++,mul=mul*p[j]%mod; if(num&1) ans=(ans+cal(mul)+mod)%mod; else ans=(ans-cal(mul)+mod)%mod; } ans=(cal(1)-ans+mod)%mod; printf("%I64d\n",ans); } return 0; }