更好的阅读体验

题目

题目描述

给定整数$N$，求$1 \le x,y \le N$且$gcd(x,y)$为素数的数对$(x,y)$有多少对。

$gcd(x,y)$即求$x，y$的最大公约数。

输入格式

输入一个整数N

输出格式

输出一个整数，表示满足条件的数对数量。

数据范围

$$ 1 \le N \le 10^7 $$

输入样例：

4

输出样例：

4

解题报告

题意理解

就是要找统计一类特殊数对.

要求两个数,他们的最大公约数为素数.

算法解析

这道题目思路比较清晰,除了算法基础课上的欧拉函数,完全没有高级数学知识,只有最大公约数,乘法这些数学知识,而且公式都非常简短,可以放心食用.违背了数学题目的常识

我们先来下定义.
$$ a=x \times d \quad x为任意正整数\\\\ b=y \times d \quad y为任意正整数\\\\ d为素数 \\\\ $$
那么什么时候才会出现
$$ gcd(a,b)=d $$
也就是题目要求统计的数对呢?

我们思索一下,什么是最大公约数,不就是两个数的最大公因子吗?

那么我们把定义放入进去.
$$ a=x \times d \\\\ b=y \times d \\\ gcd(a,b)=gcd(x \times d,y \times d)=d \\\\ gcd(a,b)=d \times gcd(x,y) $$
此时我们应该很好看出来了,一个$a,b$为合法数对的条件了.
$$ gcd(x,y)=1 \quad x,y必须互素 $$
否则的话,我们观察发现
$$ gcd(a,b)=d \times gcd(x,y) \\\\ 如果不满足gcd(x,y)=1的话 \\\\ d \times gcd(x,y) \not= d \\\\ $$
一个素数乘以一个大于1的数字,请问还有可能是素数吗?

显然是不可能的.

所以我们就证明了这个性质.

既然如此的话,我们发现了性质,那么就要推导公式了.

对于一个素数$d$而言.他在$1$~$n$中显然有这些数.
$$ d,d \times 2,d \times 3,…,d \times k. \\\\ d \times k \le n $$
我们发现$gcd(a,b)=d$的数对,只能从上面这个式子中选择.

因为最大公约数是$d$,所以必须有共同因子$d$.

那么我们再来简化数列,也就是上面式子,都抛去d.
$$ a/=d \\\\ b/=d. $$
那么$a,b$就会从下面这个数列中选择
$$ 1,2,3,…k $$
我们再来分析.

因为合法数对$a,b$都除以$d$这个最大公约数,所以此时.
$$ gcd(a,b)=d \\\ ==> gcd(a/d,b/d)=1 $$
总而言之,言而总之,我们要

在下面这个数列中,找到两个互质的数,那么一定是合法数对.
$$ 1,2,3,…k $$
比如说我们选择
$$ 2,3 $$
那么实际上对应的数字就是
$$ 2\times d,3\times d $$
因此当前的任务就是找到互质的两个数.

此时我们就需要用到这道题目唯一的难点数学知识.

欧拉函数:是小于n的正整数中与n互质的数的数目

那么我们对于一个数列而言,它的欧拉函数总和,就是两个互质数对个数.
$$ ans=\phi{1} + \phi{2} + \phi{3} +…+\phi{k} $$
不过本题目是无序数对,因此.
$$ ans \times 2 $$
因此使用线性筛法,就可以$O(n)$求出每一个$\phi{i}$

不过为了加速处理,我们还可以使用前缀和数组.
$$ sum[i]表示 \phi{1}+\phi{2}+\phi{3}+..+\phi{k}的总和 $$

代码解析

#include <bits/stdc++.h>
const int N=1e7+10;
using namespace std;
int zs[N],cnt,phi[N],n;
long long sum[N],ans;
bool st[N];
void get_phi(int n)
{
    phi[1]=1;
    for (int i=2; i<=n; i++)
    {
        if (!st[i])
        {
            zs[cnt++]=i;
            phi[i]=i-1;
        }
        for (int j=0; zs[j]<=n/i; j++)
        {
            int t=zs[j]*i;
            st[t]=true;
            if (i%zs[j]==0)
            {
                phi[t]=phi[i]*zs[j];
                break;
            }
            phi[t]=phi[i]*(zs[j]-1);
        }
    }
}
int main()
{
    scanf("%d",&n);
    get_phi(n);
    for(int i=2;i<=n;i++)
        sum[i]=sum[i-1]+phi[i];
    for(int i=0;i<cnt;i++)
    {
        int now=n/zs[i];
        ans+=sum[now]*2+1;//因为phi[1]=1,我们的前缀和没有处理.
    }
    printf("%lld\n",ans);
    return 0;
}