BZOJ2818 GCD 【莫比乌斯反演】
2024-09-04 16:53:16
2818: Gcd
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 6826 Solved: 3013
[Submit][Status][Discuss]
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
题解
一般gcd一堆求和都是莫比乌斯
我们设f(n)表示gcd等于n的对数
我们设F(n)表示n|gcd的对数
则有
F(n)=⌊Nn⌋2
f(n)=∑n|dμ(dn)F(d)
=∑n|dμ(dn)⌊Nn⌋2
=∑Ni=1μ(i)⌊Ni∗n⌋2
ans=∑Np∈prime∑Ni=1μ(i)⌊Ni∗p⌋2
=∑NT=1⌊NT⌋2∗∑Np|Tμ(Tp)
至此我们可以枚举T,之后计算后边的和式就好了
其实后边的和式可以预处理得到,我直接算也能过
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u]; k != -1; k = ed[k].nxt)
using namespace std;
const int maxn = 10000005,maxm = 100005,INF = 1000000000;
bitset<maxn> isn;
int prime[maxn],primei,miu[maxn],N;
void init(){
miu[1] = 1;
for (int i = 2; i <= N; i++){
if (!isn[i]) prime[++primei] = i,miu[i] = -1;
for (int j = 1; j <= primei && i * prime[j] <= N; j++){
isn[i * prime[j]] = true;
if (i % prime[j] == 0) {miu[i * prime[j]] = 0;break;}
miu[i * prime[j]] = -miu[i];
}
}
}
int main(){
cin>>N;
init();
LL ans = 0;
for (int i = 1; i <= primei; i++){
for (int j = 1; j <= N / prime[i]; j++)
ans += (LL) miu[j] * (N / prime[i] / j) * (N / prime[i] / j);
}
cout<<ans<<endl;
return 0;
}
最新文章
- javascript-组合模式
- [moka同学笔记]八、Yii2.0课程笔记(魏曦老师教程)[授权]
- Type.IsContextful 说明
- 修改AssemblyInfo.cs自动生成版本号
- Android爬坑之路
- Linux学习 :移植linux-4.7.4到JZ2440开发板
- 在c#中使用bitblt显示图片
- JButton计数
- Solaris从安装光盘安装软件
- Codeforces Round #363
- HDU 5813 Elegant Construction (贪心)
- My97DatePicker的calendar.js的反混淆
- The square chest
- spring mvc 安全
- ThinkPad E530 Fedora 20 无线上网问题
- 【原创】构建高性能ASP.NET站点之二 优化HTTP请求(前端)
- MySQL 常用命令大全2
- HDU 2503 a/b + c/d(最大公约数与最小公倍数,板子题)
- Log4Net在MVC下的配置以及运用线程队列记录异常信息
- exports与module.exports的区别,export与export.defult区别