BZOJ2818 - Click Here
Description
给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对。
Input
一个整数N
Output
如题
Solutions
题目要求$gcd(x,y)=k$，其中k为素数。
根据原式易得$gcd(\frac{x}{k},\frac{y}{k})=1$(由定理$n \times gcd(a,b)=gcd(na,nb)$得到，具体证明看算导)。
令$x’=\frac{x}{k},y’=\frac{y}{k}$，则能够对答案产生贡献的点对$(x’ \, , \, y’)$的必要前提是$x’ \times k \leq n,y’ \times k \leq n$，即$x’ \leq \lfloor \frac{n}{k} \rfloor \, , \, y’\leq \lfloor \frac{n}{k} \rfloor$。
因此答案为$\sum_{i=1}^{L}\sum_{j=1}^{\lfloor\frac{n}{a_i}\rfloor}\phi(j)$，其中为$a_i$质数。求出欧拉函数后用前缀和累计答案即可。
CODE
CODE - Click Here