Description

给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的

数对(x,y)有多少对.

Input

一个整数N

Output

如题

Sample Input

4

Sample Output

4

HINT

对于样例(2,2),(2,4),(3,3),(4,2)

1<=N<=10^7

题解

由题，我们需要求

$$\sum_{i=1} ^N\sum_{j=1} ^N[gcd(i,j)为质数]$$

我们不妨令$p=gcd(i,j)$，即$p$为质数，

显然我们不可能去枚举每个$i$,$j$，我们考虑去枚举每个质数$p$，原式化为

$$\sum_p\sum_{i=1}^{\lfloor {N \over p} \rfloor}\sum_{j=1}^{\lfloor {N \over p} \rfloor}[gcd(i,j)=1]$$

我们取出数对$(i,j)$

1.若$i>j$，我们发现对于式子

$$\sum_p\sum_{i=1}^{\lfloor {N \over p} \rfloor}\sum_{j=1}^{\lfloor {N \over p} \rfloor}[gcd(i,j)=1]$$

可化为

$$\sum_p\sum_{i=1}^{\lfloor {N \over p} \rfloor}\sum_{j=1}^{i-1}[gcd(i,j)=1]$$

取出

$$\sum_{i=1}^{\lfloor {N \over p} \rfloor}\sum_{j=1}^{i-1}[gcd(i,j)=1]$$

发现，这其实就是欧拉函数$φ$的定义式（先不考虑$φ(1)=1$）。

那么原式就可以化为

$$\sum_p\sum_{i=1}^{\lfloor {N \over p} \rfloor}φ(i)$$

结论。

2.若$i=j$，这种条件下只有$i=j=p$符合条件，显然最后我们只要将答案加上素数的个数就可以了。

3.若$i<j$，实际上只要交换$i$，$j$位置即可，我们只需要将1.得出的结论$×2$即可。

1 #include

其实统计答案的第二层循环可以用前缀和优化。

1 //It is made by Awson on 2018.1.12 2 #include 
     
       3 #include