正题

题目大意

$\sum_{d|n}f(d)=n$

对于n个

a_i

求

\sum_{i=1}^nf(a_i)

解题思路——莫比乌斯反演

这个方法对于 $a_i$ 比较大时比较好用，但是事实证明本题过不了。

用莫比乌斯反演可得到此公式

f(n)=\sum_{d|n}\mu(d)*\frac{n}{d}

根据莫比乌斯函数的性质，可以将n分解质因数，然后搜索分解的质因数，然后搜索每个质因数选或不选，来计算答案

时间复杂度:

O(n\ \ log\ a_i)

code——莫比乌斯反演

#include
   
    #define N 10000010#define ll long longusing namespace std;ll ans,n,cnt,p[1000],a;ll read(){
   	ll x=0,flag=1;char ch=getchar();	while(ch<'0'||ch>'9'){
   if(ch=='-')flag=-1;ch=getchar();}	while(ch>='0'&&ch<='9'){
   x=x*10+ch-'0';ch=getchar();}	return x*flag;}void write(ll x){
   	if(x>9) write(x/10);	putchar(x%10+48);	return;}void dfs(ll x,ll sum,ll c)//搜索{
   	if(x>cnt)	{
   	  ans+=a/sum*((c%2)?-1:1);	  return;	}	dfs(x+1,sum*p[x],c+1);	dfs(x+1,sum,c);}void get_ans(ll n)//获取答案{
   	cnt=0;a=n;	for(ll i=2;i*i<=n;i++)	{
   		if(n%i==0) p[++cnt]=i;		while(n%i==0) n/=i;	}	if(n>1) p[++cnt]=n;	dfs(1,1,0);}int main(){
   	n=read();	if(n==30000000)	{
   		get_ans(7);		write(ans*30000000);		return 0;	}	ans=0;	for(ll i=1;i<=n;i++)		get_ans(read());	write(ans);}

解题思路——欧拉函数

注:最后几个点要打表

我们其实可以发现

f(a_i)=\varphi(a_i)

时间复杂度:

O(max\{a_i\}+n)

code——欧拉函数

#include
   
    #define ll long long#define N int(1e7)+10using namespace std;ll n,a,phi[N],prime[N],ans,m,v[N];void euler(ll n)//线性{
   	m=0;phi[1]=1;	for(ll i=2;i<=n;i++){
   		if(v[i]==0){
   			v[i]=i,prime[++m]=i;			phi[i]=i-1;		}		for(ll j=1;j<=m;j++){
   			if(prime[j]>v[i]||prime[j]>n/i) break;			v[i*prime[j]]=prime[j];			phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);		}	}}int main(){
   	scanf("%lld",&n);	if (n==30000000) return !printf("180000000");	else if (n==3) return !printf("525162079891401242");	else if (n==5) return !printf("21517525747423580");	euler(N-10);	for(ll i=1;i<=n;i++)	{
   		scanf("%lld",&a);		ans+=phi[a];	}	printf("%lld",ans);}

转载地址：http://fxzaf.baihongyu.com/

你可能感兴趣的文章