大意：求1~n之间与n不互质的数的总和。
思路：欧拉函数的应用；先用欧拉函数求出与n互质的总数m，计算m个数的总和，用n的总和减去m的总和就是想要的结果。
1 #include <stdio.h> 2 #define LL __int64 3 4 int eular(int n){ 5 int ret = 1; 6 for(int i = 2; i*i <= n;i++) 7 if(n%i == 0){ 8 n /= i, ret *= i-1; 9 while(n%i == 0) 10 n /= i, ret *= i; 11 } 12 if(n > 1) 13 ret *= n-1; 14 return ret; 15 } 16 17 LL n, m; 18 19 int main() 20 { 21 while(~scanf("%I64d", &n) && n) 22 { 23 LL sum = n*(n+1)/2-n; ///计算所有数总数 24 LL t = eular(n)*n/2; ///计算互质的数总和 25 sum -= t; 26 sum %= 1000000007; 27 printf("%I64d ", sum); 28 } 29 30 return 0; 31 }