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