luogu2568 GCD
2024-09-30 05:47:04
先筛法求出 \([1,n]\) 间的素数,然后枚举每个素数。可以发现,对于每个素数 \(x\),它的贡献是 \([1,\lfloor n/x \rfloor]\) 间的有序互质对数。
我们钦定 \((x,y)\) 是 \(x \leq y\) 的,发现 \(x=y\) 是合法的当且仅当 \(x=y=1\)。这样就有 \(x < y\) 了。要求 \(x,y\) 互素,则想到求 \(\varphi(y)\)。
则对于一个素数 \(x\),他对答案的贡献是 \(\sum_{i=1}^{\lfloor n/x \rfloor} 2\varphi(i)-1\)。减一是因为 \((1,1)\) 被计算了两遍。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, cnt, pri[10000005];
ll ans, phi[10000005];
bool isp[10000005];
void shai(){
memset(isp, true, sizeof(isp));
isp[0] = isp[1] = false;
phi[1] = 1;
for(int i=2; i<=n; i++){
if(isp[i]){
pri[++cnt] = i;
phi[i] = i - 1;
}
for(int j=1; j<=cnt && i*pri[j]<=n; j++){
isp[i*pri[j]] = false;
if(i%pri[j]==0){
phi[i*pri[j]] = phi[i] * pri[j];
break;
}
phi[i*pri[j]] = phi[i] * (pri[j] - 1);
}
}
for(int i=2; i<=n; i++)
phi[i] += phi[i-1];
}
int main(){
cin>>n;
shai();
for(int i=1; i<=cnt; i++)
ans += 2 * phi[n/pri[i]] - 1;
cout<<ans<<endl;
return 0;
}
最新文章
- MyBatis入门案例
- 编译原理词法分析 java简单实现
- d3.js读书笔记-2
- linux学习网站分享
- varnish
- loj 1009(dfs)
- 恢复ext4文件系统superblock
- [HNOI2004]宠物收养场 Treap前驱后继
- String属于“假引用类型”,代码为证(一个String引发的血案...)
- Java使用拦截器的两种方式
- 波涛1202wm8833 lihomme/历织造 2013秋装全新男装夹克 整身年龄外套潮流立领男士休闲外套薄_9才号
- 201521123074 《Java程序设计》第7周学习总结
- ubuntu重装指定版本的mysql
- P5300 [GXOI/GZOI2019]与或和
- 多线程 Thread.yield 方法到底有什么用?
- <;转>;安全测试思维导图
- 如何使用JBDC修改数据
- C# 键值对数据排序
- hdu 4535 错排
- chrome vim设置