首页 > 代码库 > bzoj 2818: Gcd 歐拉函數
bzoj 2818: Gcd 歐拉函數
2818: Gcd
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 1633 Solved: 724
[Submit][Status]
Description
给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.
Input
一个整数N
Output
如题
Sample Input
4
Sample Output
4
HINT
hint
对于样例(2,2),(2,4),(3,3),(4,2)
1<=N<=10^7
Source
求gcd(x,y)==prime[k] 對數（1<=x,y<=n）
枚舉質數p，求gcd(x,y)==1, (1<=x,y<=n/p)
設sphi(k)表示gcd(x,y)==1,(1<=x,y<=k),那麼，可以通過幾何法推導出sphi(k)=phi(k)*2+sphi(k-1)
然後此題可解。
bzoj 2818: Gcd 歐拉函數
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。