[牛客小白月赛12]D.月月给华华出题(欧拉函数 + 数学)

发布于 2022-08-19  306 次阅读


题目传送门:D-月月给华华出题_牛客小白月赛12 (nowcoder.com)

思路 / Thought

如果按照朴素的想法,对于每一个N,用 i 遍历1~N,每一个i又用O(i)的复杂度算出ans[i],复杂度大概是O(N ^ 2 * logN),显然不行,应该找到数字之间的规律。

对于每一个数字x的所有因子d,有可能是x与某个i的最大公因数,于是我们可以改变一个角度,从因子d的角度去思考,如果gcd(i, x) == d,那么就要加上i / d,否则就不加。

再经过一系列的推导,可以得到最后的公式。

关于最后一步欧拉函数性质的解释:如果gcd(d, n) = 1,那么有gcd(d, n - d) = 1(欧几里得算法),意思是[1, n-1]中与n互质的数字都是成对出现的且每一对和为n,那么也就是平均每个数字都是n / 2。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 9;
int phi[maxn];


void init(int n)
{
	for(int i = 1;i <= n; ++ i)phi[i] = i;
	for(int i = 2;i <= n; ++ i)
		if(phi[i] == i)for(int j = i;j <= n; j += i)phi[j] = phi[j] / i * (i - 1);
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int N;cin >> N;
	init(N);
	
	vector<int> ans(N + 1, 0);
	for(int i = 1;i <= N; ++ i)//i是因子 
		for(int j = i;j <= N; j += i)ans[j] += phi[i] * i / 2;
	
	for(int i = 1;i <= N; ++ i)cout << ans[i] + 1 << '\n'; 
	
	return 0;
}