地址：

题目：

2818: Gcd

Time Limit: 10 Sec  Memory Limit: 256 MB

Submit: 6000  Solved: 2660

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

 

Source

 

思路：

1 #include 
      
        2  3 using namespace std; 4  5 #define MP make_pair 6 #define PB push_back 7 typedef long long LL; 8 typedef pair
       
         PII; 9 const double eps=1e-8;10 const double pi=acos(-1.0);11 const int K=1e7+4;12 const int mod=1e9+7;13 14 int n,cnt,mu[K],sum[K],pr[K],isp[K];15 LL ans;16 void init(int N)17 {18     mu[1]=1;19     for(int i=2;i
        
         >n;41     init(n+1);42     for(LL i=1,r;i<=n;i=r+1)43     {44         r=n/(n/i);45         ans+=(n/i)*(n/i)*(sum[r]-sum[i-1]);46     }47     cout<
         
          <