题目链接：

思路：首先用一下欧拉函数Eluar(n)求一下1-n中与n互质的质因子的个数，然后就要用到下面简单的定理了：如果gcd(n,i)==1,那么就有gcd(n,n-i)==1;

于是题目的要求是要求小于n并且与n不互质的所有数的和，这里我们可以先求与n互质的所有数的和为sum=n*(Eular(n)/2)(这里用到了上面的定理。最后所有数的和减去sum即可。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 typedef long long LL; 8 #define MOD 1000000007 9 LL n;10 11 LL Eular(LL n) {12     LL cnt=1;13     for(int i=2; i*i<=n; i++) {14         if(n%i==0) {15             cnt*=(i-1);16             n/=i;17             while(n%i==0) {18                 n/=i;19                 cnt*=i;20             }21         }22     }23     if(n>1)cnt*=(n-1);24     return cnt;25 }26 27 int main() {28     while(~scanf("%lld",&n)&&n) {29         LL ans=(n+1)*n/2-n;30         ans-=Eular(n)*n/2;31         printf("%I64d\n",(ans%MOD+MOD)%MOD);32     }33     return 0;34 }