AcWing 220. 最大公约数 | 欧拉函数
2024-09-06 16:36:49
题目描述
给定整数N,求1<=x,y<=N且GCD(x,y)为素数的数对(x,y)有多少对。
GCD(x,y)即求x,y的最大公约数。
输入格式
输入一个整数N
输出格式
输出一个整数,表示满足条件的数对数量。
数据范围
1≤N≤10^7
输入样例:
4
输出样例:
4
题解:本题要求1<=x,y<=N且GCD(x,y)为素数的数对(x,y)数量,相当于求:对于N以内的每一个素数p,1<=x,y<=N/p 中GCD(x,y)为1的数对(x,y)数量和。我们知道欧拉函数的定义是1~n中与n互质的数的个数,那么对于p,1<=x,y<=N/p 中GCD(x,y)为1的数对(x,y)数量为φ(1)+φ(2)...+φ(N/p),可以用前缀和计算。要注意:x,y大小关系无影响所以要*2,但x,y相同时只算一次所以要-1。题目就变成了求\[\sum_{p是素数}^{p≤n} 2*\sum_{i=1}^{n/p}φ(i) -1\] 也可以用\[\sum_{p是素数}^{p≤n} 2*\sum_{i=2}^{n/p}φ(i) +1\]。
代码:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e7 + ;
int v[N],prime[N];
ll sum[N],phi[N];
int cnt = ;
int main() {
int n;
scanf("%d",&n);
phi[]=;
for (int i = ; i <= n; i++) {
if(!v[i]) {
v[i] = i;prime[cnt++] = i;
phi[i] = i-;
}
for (int j = ; j < cnt; 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]-:prime[j]);
}
}
for (int i = ; i <= n; i++)
sum[i] = sum[i-]+phi[i];
ll ans = ;
for (int i = ; i < cnt; i++) {
int num = n/prime[i];
ans += *sum[num]-;
}
printf("%lld\n",ans);
return ;
}
最新文章
- 用soapUI测试webservice
- FreeBSD 无线配置
- ASP.NET MVC的TextBoxFor()和TextBox()
- 【USACO 1.3】Barn Repair
- keepalived和heartbeat区别
- visual studio 2012 has stopped working
- Atitit.&#160;Atiposter&#160;发帖机&#160;新特性&#160;poster&#160;new&#160;feature&#160;&#160;&#160;v7&#160;q39
- B - 一行盒子
- ubuntukylin(64bit)安装推荐
- 【学习笔记】【oc】类的包装类 协议 category
- (DP)House Robber
- C#高级编程三十天----泛型结构,泛型方法,泛型托付
- [SCOI2008]奖励关
- CXF安装和配置时出现Exception in thread "main" java.lang.UnsupportedClassVersionError:异常?
- springmvc请求参数异常统一处理
- 直接插入排序算法的C++实现
- P1494 [国家集训队]小Z的袜子(莫队)
- day9--队列queue
- 网页排版的时候不要忘了table标签
- Spring框架之演示JDBC的模板类