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 不用筛$\varphi$强行莫比乌斯也是很资瓷 $\sum\limits_{i=1}^{n}\sum\limits_{i=1}^{n}isprime(gcd(i,j))$ $\sum\limits_{g=1}^{n}isprime(g)\sum\limits_{g|i}\sum\limits_{g|j}[gcd(i,j)==g]$ $\sum\limits_{g=1}^{n}isprime(g)\sum\limits_{t=1}^{\lfloor\frac{n}{g}\rfloor}\mu(t)\sum\limits_{i=1}^{\frac{n}{gt}}\sum\limits_{j=1}^{\frac{n}{gt}}1$ $\sum\limits_{p=1}^{n}\lfloor\frac{n}{p}\rfloor^{2}*\sum\limits_{g|p} isprime(g)*\mu(\frac{p}{g})$

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论