求出小於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;
}
