BZOJ 最大公约数 (通俗易懂&效率高&欧拉函数)
题目
题目描述
给定整数\(N\)，求\(1 \le x,y \le N\)且\(gcd(x,y)\)为素数的数对\((x,y)\)有多少对。
\(gcd(x,y)\)即求\(x，y\)的最大公约数。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。输入格式
输入一个整数N
输出格式
输出一个整数，表示满足条件的数对数量。
数据范围
\[ 1 \le N \le 10^7 \]
输入样例：
4输出样例：
4解题报告
关于本题
这道题目,在蒟蒻我花费了30min一顿瞎搞AC后,然后想要看网络上的题解,都是一些什么莫比乌斯反演,吓了一跳.
原题:最大公约数
大佬团:这道题目当然要莫比乌斯反演性质推导啊,这样时间效率特别高.
蒟蒻我:我只用了一个欧拉函数+前缀和瞎搞.
然后蒟蒻我想要感受一下,传说中的省选高端数学算法,莫比乌斯反演的效率.
于是我测试了一下代码.
莫比乌斯反演算法,花费4000+ms.
欧拉函数算法,花费933ms.
蒟蒻我,一脸懵逼.
后来我又搜索了这道题目的另外一个100%相似版本,终于看到了类似的算法,但是为什么处理方式那么诡异啊,网上都是\(ans \times 2-1\),我是\(ans \times 2+1\)
可能我的打开方式不对吧............
题意理解
就是要找统计一类特殊数对.
要求两个数,他们的最大公约数为素数.
算法解析
这道题目思路比较清晰,除了算法基础课上的欧拉函数,完全没有高级数学知识,只有最大公约数,乘法这些数学知识,而且公式都非常简短,可以放心食用.违背了数学题目的常识
我们先来下定义.
\[ a=x \times d \quad x为任意正整数\\\\ b=y \times d \quad y为任意正整数\\\\ d为素数 \\\\ \]
那么什么时候才会出现
\[ gcd(a,b)=d \]
也就是题目要求统计的数对呢?
我们思索一下,什么是最大公约数,不就是两个数的最大公因子吗?
那么我们把定义放入进去.
\[ a=x \times d \\\\ b=y \times d \\\ gcd(a,b)=gcd(x \times d,y \times d)=d \\\\ gcd(a,b)=d \times gcd(x,y) \]
此时我们应该很好看出来了,一个\(a,b\)为合法数对的条件了.
\[ gcd(x,y)=1 \quad x,y必须互素 \]
否则的话,我们观察发现
\[ gcd(a,b)=d \times gcd(x,y) \\\\ 如果不满足gcd(x,y)=1的话 \\\\ d \times gcd(x,y) \not= d \\\\ \]
一个素数乘以一个大于1的数字,请问还有可能是素数吗?
显然是不可能的.
所以我们就证明了这个性质.
既然如此的话,我们发现了性质,那么就要推导公式了.
对于一个素数\(d\)而言.他在\(1\)~\(n\)中显然有这些数.
\[ d,d \times 2,d \times 3,...,d \times k. \\\\ d \times k \le n \]
我们发现\(gcd(a,b)=d\)的数对,只能从上面这个式子中选择.
因为最大公约数是\(d\),所以必须有共同因子\(d\).
那么我们再来简化数列,也就是上面式子,都抛去d.
\[ a/=d \\\\ b/=d. \]
那么\(a,b\)就会从下面这个数列中选择
\[ 1,2,3,...k \]
我们再来分析.
因为合法数对\(a,b\)都除以\(d\)这个最大公约数,所以此时.
\[ gcd(a,b)=d \\\ ==> gcd(a/d,b/d)=1 \]
总而言之,言而总之,我们要
在下面这个数列中,找到两个互质的数,那么一定是合法数对.
\[ 1,2,3,...k \]
比如说我们选择
\[ 2,3 \]
那么实际上对应的数字就是
\[ 2\times d,3\times d \]
因此当前的任务就是找到互质的两个数.
此时我们就需要用到这道题目唯一的难点数学知识.
欧拉函数:是小于n的正整数中与n互质的数的数目
那么我们对于一个数列而言,它的欧拉函数总和,就是两个互质数对个数.
\[ ans=\phi{1} + \phi{2} + \phi{3} +...+\phi{k} \]
不过本题目是无序数对,因此.
\[ ans \times 2 \]
因此使用线性筛法,就可以\(O(n)\)求出每一个\(\phi{i}\)
不过为了加速处理,我们还可以使用前缀和数组.
\[ sum[i]表示 \phi{1}+\phi{2}+\phi{3}+..+\phi{k}的总和 \]
代码解析
//代码是单数据版本的
#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\n",ans);
return 0;
}
