HDU 3501 Calculation 2 （欧拉函数||容斥原理）

求出小于N的与N不互质的数的和。
与N不互质，就与N肯定有相同的因子。
首先将N因式分解，找出所有的质因子。
对于某一个质因子p,有p,2*p,3*p,……k*p （k*p<=n&&(k+1)*p>n）
这是一个等差数列，容易求和。
不过可以发现有的计算了多次。这里就需要容斥原理
Ai集合为pi的倍数的集合，普通的容斥不解释。
[cpp] 
#include<iostream> 
#include<cstring> 
#include<queue> 
#include<cstdio> 
#include<cmath> 
#include<algorithm> 
#define N 100005 
#define inf  1<<30 
#define MOD 1000000007 
#define LL long long 
#define eps 1e-7 
#define zero(a) fabs(a)<eps 
#define equal(a,b) zero(a-b) 
using namespace std; 
bool flag[40000]; 
int cnt=0,prime[40000]; 
void Prime(){ 
    for(int i=2;i<=sqrt(1000000001.0);i++){ 
        if(flag[i]) 
            continue; 
        prime[cnt++]=i; 
        for(int j=2;j*i<=sqrt(1000000001.0);j++) 
            flag[i*j]=true; 
    } 
} 
LL n,temp; 
int fac[10005],tot; 
LL get_sum(int k){ 
    LL a=k,b=k+1; 
    if(!(a&1)) 
        a/=2; 
    else 
        b/=2; 
    return (a*b)%MOD; 
} 
LL ans=0; 
void dfs(LL num,int pre,int idx,int m){ 
    if(pre==m){ 
        LL tmp=(num*get_sum((temp-1)/num))%MOD; 
        if(m&1) 
            ans=(ans+tmp)%MOD; 
        else 
            ans=(ans-tmp+MOD)%MOD; 
        return ; 
    } 
    if(idx>=tot) 
        return ; 
    dfs(num,pre,idx+1,m); 
    dfs(num*fac[idx],pre+1,idx+1,m); 
} 
int main(){ 
    Prime(); 
    while(scanf("%lld",&n)!=EOF&&n){ 
        tot=0; 
        temp=n; 
        for(int i=0;i<cnt&&prime[i]<=n;i++) 
            if(n%prime[i]==0){ 
                fac[tot++]=prime[i]; 
                while(n%prime[i]==0) 
                    n/=prime[i]; 
            } 
        if(n>1) 
            fac[tot++]=n; 
        ans=0; 
        for(int i=1;i<=tot;i++) 
            dfs(1,0,0,i); 
        printf("%lld/n",ans); 
    } 
    return 0; 
} 

结果AC后百度发现竟然欧拉函数就可以过，太神了。
小于N的与N互质的数的和为eular(n)*n/2，然后用总和减掉就行了。。。
[cpp] 
#include<iostream> 
#include<cstring> 
#include<queue> 
#include<cstdio> 
#include<cmath> 
#include<algorithm> 
#define N 100005 
#define inf  1<<30 
#define MOD 1000000007 
#define LL long long 
#define eps 1e-7 
#define zero(a) fabs(a)<eps 
#define equal(a,b) zero(a-b) 
using namespace std; 
LL get_eular(LL n){ 
    LL ret=1; 
    for(int i=2;i*i<=n;i++) 
        if(n%i==0){ 
            ret*=i-1; 
            n/=i; 
            while(n%i==0){ 
                n/=i; 
                ret*=i; 
            } 
        } 
    if(n>1) 
        ret*=n-1; 
    return ret; 
} 
LL n; 
int main(){ 
    while(scanf("%I64d",&n)!=EOF&&n){ 
        LL ans=(LL)(n*(n+1))/2-n; 
        ans=ans-n*get_eular(n)/2; 
        printf("%I64d/n",(ans%MOD+MOD)%MOD); 
    } 
    return 0; 
} 

 

作者：ACM_cxlove