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

补充：软件开发 , C++ ,