Calculation 2Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1241 Accepted Submission(s): 518
Problem DescriptionInputOutputSample InputSample OutputAuthorSource/* if gcd(n,i)==1 then gcd(n,n-i)==1 所以 那么对于n有phi(n)(欧拉函数)个小于n的数与n互质 由上面的公式可以知道 其中一个若为i则存在一个为n-i那么2者之和为n 这样的一共有phi(n)/2对 故与n互质的所有数的和为 n*phi(n)/2那么与n不互质的 数就是(1+n-1)*(n-1)/2-n*phi(n)/2*/#include<stdio.h>#include<math.h>#define mod 1000000007__int64 get_phi(__int64 x)// 就是公式 { __int64 i, res=x; for (i = 2; i <(__int64)sqrt(x * 1.0) + 1; i++) if(x%i==0) { res = res / (__int64)i * (i - 1); while (x % i == 0) x /= i; // 保证i一定是素数 } if (x > 1) res = res / (__int64)x * (x - 1);//这里小心别溢出了 return res; } int main(){__int64 n,ans;while(scanf("%I64d",&n)!=EOF){if(!n) break;ans=((__int64)(1+n-1)*(n-1)/2-(__int64)n*get_phi(n)/2)%mod;//不能先除2再乘printf("%I64d\n",ans%mod);}return 0;}