ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年8月19日 177点热度 0人点赞 0条评论

题目传送门: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ 思维 数学 欧拉函数 牛客网 算法竞赛
最后更新:2022年8月19日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 思路 / Thought
  • 代码 / Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号