题目

Description

给定整数 $N$ ，求 $1 \leq x,y \leq 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 \leq N \leq 10^7$

分析

我们设 $f(n)$ 为 $gcd(x,y)=n$ 的对, $F(n)$ 为 $gcd(x,y)$ 为 $n$ 的倍数的对数,然后利用莫比乌斯反演定理,将mu函数带进来。

首先枚举每一个质数,答案就是
$$ans=\sum_{p}^{min(n,m)} \sum_{d=1}^{min(n,m)} \mu(d) \left\lfloor\frac{n}{pd}\right\rfloor \left\lfloor\frac{m}{pd}\right\rfloor$$

当然不能直接这样做,需要优化,否则就会TLE。

令 $pd=T$ ,那么有
$$ans=\sum_{T=1}^{min(n,m)}\left\lfloor\frac{n}{T}\right\rfloor \left\lfloor\frac{m}{T}\right\rfloor \sum_{p|T} \mu(\frac{T}{p})$$

如果能求出 $\sum_{p|T}\mu(\frac{T}{p})$ 的前缀和，这个问题就能在 $O(\sqrt n)$ 的时间解出。

只需要暴力枚举出每一个质数，去更新这个质数的倍数即可。

由 $\lim_{n\rightarrow \infty} \sum_{i=1}^{n}\frac{1}{i}=\ln n+r$ 这个结论易知每个质数更新时是均摊 $O(\log n)$ 的,而质数的个数恰好为 $O(n/\log n)$

故暴力枚举+维护前缀和的时间复杂度为 $O(n)$。

此题还可以用欧拉筛求素数表。

模板

const int MAXN=100010;
bool vis[MAXN];
int tot,phi[MAXN],prime[MAXN];
void CalPhi(int n)
{
    clr(vis,0);
    phi[1]=1;
    tot=0;
    for(int i=2;i<n;i++)
    {
        if(!vis[i])
        {
            prime[tot++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<tot;j++)
        {
            if(i*prime[j]>n) break;
            vis[i*prime[j]] == 1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i] * prime[j];
                break;
            }
            else phi[i*prime[j]]=phi[i] * (prime[j]-1);
        }
    }
}

得到欧拉函数phi[],素数表prime[],素数个数tot传入n为函数定义域上界。

代码

莫比乌斯反演

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<cstdlib>
#include<functional>
#include<climits>
#include<cctype>
#include<iomanip>
#include<bitset>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define clr(a,x) memset(a,x,sizeof(a))
const double eps = 1e-6;
const int mod = 1e9+7;
const int MAXN=10000010;
int a[MAXN]={1,1},b[MAXN/10],mu[MAXN],cnt;
void init()
{
    ll i,j;
    mu[1]=1;
    for(int i=2;i<MAXN;i++)
    {
        if(a[i]==0)
        {
            b[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&b[j]*i<MAXN;j++)
        {
            a[b[j]*i]=1;
            if(i%b[j]==0)
            {
                mu[b[j]*i]=0;
                break;
            }
            else
            {
                mu[b[j]*i]=-mu[i];
            }
        }
    }
}
int main()
{
    init();
    int n;
    ll ans=0;
    scanf("%d",&n);
    for(int i=1;i<=cnt&&b[i]<=n;i++)
    {
        ll sum=0;
        for(int j=b[i];j<=n;j+=b[i])
            sum+=(ll)mu[j/b[i]]*(n/j)*(n/j);
        ans+=sum;
    }
    printf("%lld\n",ans);
    return 0;
}

欧拉筛(详细解释看这里)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<cstdlib>
#include<functional>
#include<climits>
#include<cctype>
#include<iomanip>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define clr(a,x) memset(a,x,sizeof(a))
const double eps = 1e-6;
const int mod = 1e9+7;
const int MAXN=1e7 + 5;
bool vis[MAXN];
int tot,phi[MAXN],prime[MAXN];

//refer to CSL

void CalPhi(int n)
{
    clr(vis,0);
    phi[1]=1;
    tot=0;
    for(int i=2;i<n;i++)
    {
        if(!vis[i])
        {
            prime[tot++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<tot;j++)
        {
            if(i*prime[j]>n) break;
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}
ll a[MAXN];
int main()
{
    int n;
    ll ans=0;
    scanf("%d",&n);
    CalPhi(n);
    a[1]=1;
    for(int i=2;i<=n;i++)
        a[i]=a[i-1]+2*phi[i];
    for(int i=0;i<tot;i++)
        if(n/prime[i])
            ans+=a[n/prime[i]];
    printf("%lld\n",ans);
    return 0;
}