题目
题目描述
给定整数(N)，求(1 le x,y le N)且(gcd(x,y))为素数的数对((x,y))有多少对。
(gcd(x,y))即求(x，y)的最大公约数。
输入格式
输入一个整数N
输出格式
输出一个整数，表示满足条件的数对数量。
数据范围
输入样例：
4
输出样例：
4
解题报告
关于本题
这道题目,在蒟蒻我花费了30min一顿瞎搞AC后,然后想要看网络上的题解,都是一些什么莫比乌斯反演,吓了一跳.
原题:最大公约数
大佬团:这道题目当然要莫比乌斯反演性质推导啊,这样时间效率特别高.
蒟蒻我:我只用了一个欧拉函数+前缀和瞎搞.
然后蒟蒻我想要感受一下,传说中的省选高端数学算法,莫比乌斯反演的效率.
于是我测试了一下代码.
莫比乌斯反演算法,花费4000+ms.
欧拉函数算法,花费933ms.
蒟蒻我,一脸懵逼.
后来我又搜索了这道题目的另外一个100%相似版本,终于看到了类似的算法,但是为什么处理方式那么诡异啊,网上都是(ans imes 2-1),我是(ans imes 2+1)
可能我的打开方式不对吧............
题意理解
就是要找统计一类特殊数对.
要求两个数,他们的最大公约数为素数.
算法解析
这道题目思路比较清晰,除了算法基础课上的欧拉函数,完全没有高级数学知识,只有最大公约数,乘法这些数学知识,而且公式都非常简短,可以放心食用.违背了数学题目的常识
我们先来下定义.
那么什么时候才会出现
也就是题目要求统计的数对呢?
我们思索一下,什么是最大公约数,不就是两个数的最大公因子吗?
那么我们把定义放入进去.
此时我们应该很好看出来了,一个(a,b)为合法数对的条件了.
否则的话,我们观察发现
一个素数乘以一个大于1的数字,请问还有可能是素数吗?
显然是不可能的.
所以我们就证明了这个性质.
既然如此的话,我们发现了性质,那么就要推导公式了.
对于一个素数(d)而言.他在(1)~(n)中显然有这些数.
我们发现(gcd(a,b)=d)的数对,只能从上面这个式子中选择.
因为最大公约数是(d),所以必须有共同因子(d).
那么我们再来简化数列,也就是上面式子,都抛去d.
那么(a,b)就会从下面这个数列中选择
我们再来分析.
因为合法数对(a,b)都除以(d)这个最大公约数,所以此时.
总而言之,言而总之,我们要
在下面这个数列中,找到两个互质的数,那么一定是合法数对.
比如说我们选择
那么实际上对应的数字就是
因此当前的任务就是找到互质的两个数.
此时我们就需要用到这道题目唯一的难点数学知识.
欧拉函数:是小于n的正整数中与n互质的数的数目
那么我们对于一个数列而言,它的欧拉函数总和,就是两个互质数对个数.
不过本题目是无序数对,因此.
因此使用线性筛法,就可以(O(n))求出每一个(phi{i})
不过为了加速处理,我们还可以使用前缀和数组.
代码解析
//代码是单数据版本的
#include <bits/stdc++.h>
const int N=1e7+10;
using namespace std;
int zs[N],cnt,phi[N],n;
long long sum[N],ans;
bool st[N];
void get_phi(int n)
{
phi[1]=1;
for (int i=2; i<=n; i++)
{
if (!st[i])
{
zs[cnt++]=i;
phi[i]=i-1;
}
for (int j=0; zs[j]<=n/i; j++)
{
int t=zs[j]*i;
st[t]=true;
if (i%zs[j]==0)
{
phi[t]=phi[i]*zs[j];
break;
}
phi[t]=phi[i]*(zs[j]-1);
}
}
}
int main()
{
scanf("%d",&n);
get_phi(n);
for(int i=2;i<=n;i++)
sum[i]=sum[i-1]+phi[i];
for(int i=0;i<cnt;i++)
{
int now=n/zs[i];
ans+=sum[now]*2+1;//因为phi[1]=1,我们的前缀和没有处理.
}
printf("%lld
",ans);
return 0;
}