牛客小白月赛12 D-月月给华华出题(数论/欧拉函数性质+埃筛思想)

题目

输入一个n(n<=1e6)

对每个1<=i<=n，回答的值

思路来源

官方题解

https://ac.nowcoder.com/discuss/160376?type=101&order=0&pos=5&page=1

关于最后一步欧拉函数性质的证明

https://blog.****.net/qq_40861876/article/details/81530231

http://tieba.baidu.com/p/3671280177

官方题解

求原式，可以枚举因数d

对于每个因数d来说，d的贡献是从1到N的数中和N的最大公因数为d的数的和

[gcd(i,N)==d]代表若中括号内式子成立则为1，否则为0

将d提出来，就是(从1到N/d的数中和N/d的最大公因数为1的数的和)*d

约去d之后，就是枚举因数d，求从1到N/d的数中和N/d互质的数的和

因数d计入N/d的贡献，那么因数N/d一定会计入d的贡献，

二者成对出现，互相计对方的贡献，

那么，为什么不自己计自己的贡献呢，

所以这与枚举因数d，因数d计入因数d的贡献是一样的，

然后就只剩倒数第二步到倒数第一步的化简了

 

注意到，gcd(n,m)等于1时，gcd(n,n-m)也等于1

证明：

反证法，

设gcd(n,m)=1时，有gcd(n,n-m)=k>1，

则n=a*k,n-m=b*k，有m=(a-b)*k，

则gcd(n,m)>=k>1，与假设矛盾，故gcd(n,n-m)=1

 

故与n互质的数成对出现且和为n，

与n互质的数共有个，两两凑对知，

比n小且与n互质的数的和为​​​​​​​

考虑到n==1时答案为1，故将其统一为

算d对每个N的贡献时，埃筛把d的贡献加上就行

心得

要入坑狄利克雷卷积、莫比乌斯反演和杜教筛了

数论基础要打好啊，加油鸭！！！

代码

#include<iostream>
#include<cstdio>
#include<cstring> 
const int maxn=1e6+10;
typedef long long ll;
bool ok[maxn];
int prime[maxn],phi[maxn],cnt;
int n;
ll ans[maxn];
void sieve()
{ 
    phi[1]=1;
	for(ll i=2;i<maxn;++i)
	{
		if(!ok[i])
		{
			prime[cnt++]=i;
			phi[i]=i-1;
		}
		for(int j=0;j<cnt;++j)
		{
			if(i*prime[j]>=maxn)break;
			ok[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				phi[i*prime[j]]=phi[i]*prime[j];//prime[j]是i的因子 prime[j]的素因子项包含在i的素因子项里
				break; 
			}
			else phi[i*prime[j]]=phi[i]*(prime[j]-1);//prime[j]与i互质 phi[i*prime[j]=phi[i]*phi[prime[j]]
		}
	}
}
void solve()
{
	for(ll i=1;i<=n;++i)
	{
		for(int j=i;j<=n;j+=i)
		{
			if(i==1)ans[j]++;
			else ans[j]+=phi[i]*i/2;
		}
	}
	for(int i=1;i<=n;++i)
	printf("%lld\n",ans[i]);
}
int main()
{
	sieve();
	scanf("%d",&n);
	solve();
	return 0;
}