题目

题目描述

若两个数的最大公约数为1，则这两个数互质。现在给出一个正整数N（1<=2^31-1)，你的任务是求出1~N中与N互质的数的总和。

输入

一个整数N

输出

一个整数sum，表示1~N中与N互质的数的总和。

样例输入

10

样例输出

20

---

分析

解法一

套公式：ans=N*phi(N)/2

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;long long zs[1000],m,ans,m2[20];long long s;int main(){ long long k,p,l,n,tot; scanf("%lld",&n); int i,j; ans=(1+n)*n/2; tot=0; int nn=n; for(i=2;i<=int(sqrt(n))+1;i++) { if(n%i==0) { zs[++tot]=i; while(n%i==0) { n/=i; } } } //以上是求质因数 if(n>1) { zs[++tot]=n; } s=nn; for(i=1;i<=tot;i++) { s=(zs[i]-1)*s/zs[i]; } s=s*nn/2; printf("%lld",s);}
         
        
       
      
     
    

解法二

假设S为1~N的总和，P为与N互质的数的总和（即答案），Q为不与N互质的数的总和，则P=S-Q；

显然S=(1+N)*N/2，我们就可以通过求出Q来的得出P。

首先求出N所有的质因数，再根据容斥原理就可以很轻松的求出Q。

再因为：

2*3*5*7*11*13*17*19*23=223092870
    
     maxN
    

所以N质因数的个数不会超过9个，即容斥原理不会超时。