2818:GCD
Description
给定整数$N$，求$1\le x,y\le N$且$\gcd{x,y}$为素数的数对$(x,y)$有多少对.
Input
$N$
Output
RT
Sample
Input
----------------
4 Output
----------------
4
Hint
4个解为$(2,2)$,$(3,3)$,$(2,4)$,$(4,2)$
$1\le N\le 10^7$
Source
这道题目很有意思.
我们将一个数$A$质因数分解:$A=p_1^{m_1}p_2^{m_2}\dots p_n^{m_n}$其中$p_i$是连续素数,记为$FS(A)=\left[m_1,m_2\dots\right]$.对于每一个数来说他们的分解都是唯一的(算术基本定理).
我们将$FS(A)=a$的反函数记为$SF(a)=A$.
那么$\gcd{A,B}=SF([(\min{FS(A)[0],FS(B)[0]}),\dots])$.
那么,易证$\gcd{\frac{A}{m},\frac{B}{m}}=\frac{\gcd{a,b}}{m}$.
因此,我们可以将原问题稍稍转化下,我们可以求$1\le x,y\le \lfloor\frac{N}{p}\rfloor$(其中$p$是一个素数)时$\gcd{x,y}=1$的组数.注意到这个问题中$x,y$互质,那么我们从下到大枚举$y$,算出$\phi(y)$的和相加.由于考虑顺序,组数要乘以$2$,由于$(1,1)$正反是一样的,那么再减去$1$.
如何求$\phi(y)$呢?我们可以用线性筛法稍微改动一下.具体的看我程序.
剩下的也不难想到了.我们前缀和了$\phi(y)$,那么对于每个素数的计算就变成$O(1)$了.
#include <cstdio>
int N,i,j,k,phi[10000001],primes[700000],pr;
long long phipref[10000001],res;
int np[10000001];
void genPhi(int n){
phipref[1]=phi[1]=1;
for(i=2;i<=n;++i){
if(!np[i]){
phi[i]=i-1;
np[i]=primes[pr++]=i;
}
for(j=0;j<pr && (k=primes[j]*i)<=n;++j){
np[k]=primes[j];
if(np[i]==primes[j]){
phi[k]=phi[i]*primes[j];
break;
}else{
phi[k]=phi[i]*(primes[j]-1);
}
}
phipref[i]=phipref[i-1]+phi[i];
}
}
int main(){
scanf("%d",&N);
genPhi(N);
for(i=0;i<pr;++i) res+=phipref[N/primes[i]]*2-1;
printf("%lld\n",res);
return 0;
}
* 类似题目:BZOJ 2190 < 这道题我不清楚原做法是怎么样的0.0,数据范围开小了太多.