Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 840????Accepted Submission(s): 371
3 4 0
?
Sample Output0 2?
????????题目大意:给你一个N,求小于等于N的不互质的数的总和。
?????欧拉公式的引伸:小于或等于n的数中,与n互质的数的总和为:φ(x) * x / 2。(n>1) 所以:res =?n*(n-1)/2-n?- phi[x]*x/2。 ??????? 主要考对欧拉公式和欧拉定理的推广和理解,不多说,代码。 链接:http://acm.hdu.edu.cn/showproblem.php?pid=3501 代码:
?
#include <iostream> #include <stdio.h> #include <memory.h> using namespace std; typedef long long LL; int eular(LL n) //欧拉函数 { int i, ans = n; for(i = 2; i * i <= n; i++) { if(n%i == 0) { ans -= ans/i; while(n%i == 0) n /= i; } } if(n > 1) ans -= ans/n; return ans; } int main() { LL n, ans; while(scanf("%I64d", &n), n) { ans = n * (n+1) / 2 - n; //总和 ans -= eular(n) * n / 2; //减去互质的总和公式 ans %= 1000000007; //再取模 printf("%I64d\n", ans); } return 0; }
?