眾所周知 若（n,x）= 1,則 （n,n-x）=1;

所以只需求出n的歐拉函數值，則1~n-1中與n互素的和為m = Euler（n）* n ?/ 2;

那么不互素的和為n*（n-1）/ 2 ?- m;

#include<stdio.h> #include<math.h> typedef __int64 LL; const LL mod = 1000000007; LL Euler(LL x) {LL res = x;for(int i = 2;i <= sqrt(x);i++){if(x%i==0){while(x%i==0) x/=i;res = res/i*(i-1)%mod;}}if(x > 1) res = res/x*(x-1)%mod;return res; } int main() {LL n;while(scanf("%I64d",&n),n){LL m = Euler(n);printf("%I64d\n",(((n*(n-1)/2)%mod - m*n/2%mod)+mod)%mod);} }

總結

以上是生活随笔為你收集整理的hdu-Calculation 2(欧拉函数)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。