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

HYSBZ - 2818

Input

一个整数N

Output

如题

Sample Input

4

Sample Output

4

Hint

 

hint

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

 

1<=N<=10^7

又是莫比乌斯套路题

主要是把模板放这里

能求mobius

能求prime

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e7+5;
int mu[MAXN];
typedef long long LL;
bool check[MAXN+10];
long long prime[MAXN+10];
void Moblus()
{
    memset(check,false,sizeof(check));
    mu[1] = 1;
    long long tot = 0;
    for(long long i = 2; i <= MAXN; i++)
    {
        if( !check[i] )
        {
            prime[tot++] = i;
            mu[i] = -1;
        }
        for(long long j = 0; j < tot; j++)
        {
            if(i * prime[j] > MAXN) break;
            check[i * prime[j]] = true;
            if( i % prime[j] == 0)
            {
                mu[i * prime[j]] = 0;
                break;
            }
            else
            {
                mu[i * prime[j]] = -mu[i];
            }
        }
    }
}


int main()
{
    Moblus();
    long long a;
    cin>>a;
    long long ans=0;
    for(int t=0;prime[t]<=a;t++)
    {
       for(int i=prime[t];i<=a;i+=prime[t])
       {
           ans+=mu[i/prime[t]]*(a/i)*(a/i);
       }
    }
    cout<<ans;
}