所有点对最短路径问题(S2oj337)

标签： 线性筛，欧拉函数

对于 $gcdgcd$ 不为 $11$ 的点对，距离显然为 $11$

否则考虑寻找过渡点。这里设 $p_{x}p\_x$ 表示 $xx$ 的最小质因子，可以通过线性筛得到

1. 只有一个过渡点(距离为 $22$）：

   ​ 那这个过渡点和两点的 $gcdgcd$ 都不为 $11$，显然 $p_x{p}_{y}p\_xp\_y$ 是 $xx$ 和 $yy$ 之间的最小过渡点， 所以两点距离为 $22$ 当且仅当 $p_x{p}_y\le n\wedge \gcd (x,y)=1p\_xp\_y\; \backslash leq\; n\; \backslash land\; \backslash gcd(x,y)\; =\; 1$

2. 有两个过渡点(距离为 $33$) :

   ​ 这两个点的距离既不 $11$ 又不是 $22$ ，所以 $p_x\times p_y>n\wedge gcd(x,y)=1p\_x\backslash times\; p\_y\; >\; n\; \backslash land\; gcd(x,\; y)\; =\; 1$, 而这两个过渡点最小肯定是 $2p_{x}2p\_x$ 和 $2p_{y}2p\_y$ 所以两点距离为 $33$ 当且仅当 $p_x\times p_y>n\wedge gcd(x,y)=1\wedge 2p_x\le n\wedge 2p_y\le np\_x\backslash times\; p\_y\; >\; n\; \backslash land\; gcd(x,\; y)\; =\; 1\; \backslash land\; 2p\_x\; \backslash leq\; n\; \backslash land\; 2p\_y\; \backslash leq\; n$ .

3. 有多个过渡点(距离为 $3^{+}3^+$) :

   ​ 两个过渡点无法连接的点，更多的过渡点一定也无法连接，因为 $2p_x\mathrm{和}2p_{y}2p\_x\; 和\; 2p\_y$ 为可以与两个点相连且可以互相相连的最小的点。

4. 无法连接：

   ​ 那就是说 $nn$ 以内不存在过渡点和这两个点相连，且这两个点不直接相连。即 $2p_x>n\wedge 2p_y>n2p\_x\; >\; n\; \backslash land\; 2p\_y\; >\; n$ ，所以它一定是质数。$p_x=xp\_x\; =\; x$

   如果他是合数的话 $2p_x\le x\le n2p\_x\; \backslash leq\; x\; \backslash leq\; n$ 不符合条件

对于直接相连的点， 一共有 ${\sum }_{i=1}^n{\sum }_{j=1}^{i-1}[\gcd (i,j)\mathrm{\ne }1]\backslash sum\_\{i=1\}^\{n\}\backslash sum\_\{j=1\}^\{i-1\}\; [\backslash gcd(i,j)\; \backslash neq\; 1]$ 对 ${\sum }_{i=1}^n{\sum }_{j=1}^{i-1}[\gcd (i,j)\mathrm{\ne }1]=\frac{n\times (n-1)}{2}-{\sum }_{i=1}^n{\sum }_{j=1}^{i-1}[\gcd (i,j)=1]=\frac{n\times (n-1)}{2}-{\sum }_{i=2}^n\varphi (i)\backslash sum\_\{i=1\}^\{n\}\backslash sum\_\{j=1\}^\{i-1\}\; [\backslash gcd(i,j)\; \backslash neq\; 1]\backslash \backslash \; =\backslash frac\{n\backslash times\; (n\; -\; 1)\}\{2\}\; -\; \backslash sum\_\{i=1\}^\{n\}\backslash sum\_\{j=1\}^\{i-1\}\; [\backslash gcd(i,j)\; =\; 1]\backslash \backslash \; =\backslash frac\{n\backslash times\; (n\; -\; 1)\}\{2\}\; -\; \backslash sum\_\{i=2\}^\{n\}\backslash phi(i)$

对于距离为 $22$ 的点，我不是很会求， 但是用总点对数减去其他三种情况就好了。

对于距离为 $33$ 的点，$p_x\times p_y>n\wedge gcd(x,y)=1\wedge 2p_x\le n\wedge 2p_y\le np\_x\backslash times\; p\_y\; >\; n\; \backslash land\; gcd(x,\; y)\; =\; 1\; \backslash land\; 2p\_x\; \backslash leq\; n\; \backslash land\; 2p\_y\; \backslash leq\; n$ 条件好多， 一个一个看。

考虑枚举 $xx$ 找 $yy$ 的数量.

$2p_x\le n2p\_x\; \backslash leq\; n$ 直接判断 $xx$ 是否符合条件.

$p_x\times p_y>n\wedge 2p_y\le np\_x\backslash times\; p\_y\; >\; n\; \backslash land\; 2p\_y\; \backslash leq\; n$ 我们得到 , 可以预处理出这个范围内 $p_{y}p\_y$ 的数量

$gcd(x,y)=1gcd(x,\; y)\; =\; 1$ 如果要满足这个条件，满足要求的 $p_{y}p\_y$ 就不会在一段连续的区间内， 但是 $p_x\times p_y>np\_x\; \backslash times\; p\_y\; >\; n$ , 假设$gcd(x,y)=p_{z}gcd(x,\; y)\; =\; p\_z$ 那么 $p_z\ge p_x\wedge p_z\ge p_{y}p\_z\; \backslash geq\; p\_x\; \backslash land\; p\_z\; \backslash geq\; p\_y$ , 所以 $p_x\times p_z>n\wedge p_y\times p_z>np\_x\; \backslash times\; p\_z\; >\; n\; \backslash land\; p\_y\; \backslash times\; p\_z\; >\; n$ 不符合题意. 所以只要$p_x\times p_y>np\_x\; \backslash times\; p\_y\; >\; n$，$gcd(x,y)gcd(x,\; y)$ 就等于 $11$， 但是注意排除$p_x=p_{y}p\_x\; =\; p\_y$ 的情况 我们只要在 时减去 $p_{x}p\_x$ 的数量即可

所以我们只需要满足 $2p_x\le n\wedge p_x\times p_y>n\wedge 2p_y\le n\wedge p_x\mathrm{\ne }{p}_{y}2p\_x\; \backslash leq\; n\; \backslash land\; p\_x\backslash times\; p\_y\; >\; n\; \backslash land\; 2p\_y\; \backslash leq\; n\; \backslash land\; p\_x\; \backslash neq\; p\_y$,

对于无法连接的点对， 预处理出关于质数个数的前缀和 $sumsum$。点对数为$n-1+{\sum }_{i\mathrm{是}\mathrm{质}\mathrm{数}\wedge 2i>n}^{n}n-1-(su{m}_i-su{m}_{\frac{n}{2}})n\; -\; 1\; +\; \backslash sum\_\{i是质数\backslash land\; 2i\; >\; n\}^n\; n\; -\; 1\; -\; (sum\_i\; -\; sum\_\backslash frac\{n\}\{2\})$, $11$ 和除它以外的任何数 $gcdgcd$ 都是 $11$.

Code :

#include <iostream>
#include <cstdio>
#define ll long long

using namespace std;

const int N = 1e7 + 10;
ll len[5];
int vis[N], phi[N], pri[N], tot, p[N], nump[N];
int sum[N];
int n;

void euler(int n)
{
    phi[1] = 1;
    vis[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (!vis[i]) pri[++tot] = i, phi[i] = i - 1, p[i] = i;
        for (int j = 1; j <= tot && pri[j] * i <= n; ++j)
        {
            vis[i * pri[j]] = 1;
            p[i * pri[j]] = pri[j];
            if (i % pri[j] == 0)
            {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            }
            phi[i * pri[j]] = phi[i] * phi[pri[j]];
        }
    }
}

int main()
{
    scanf("%d", &n);
    // 特判
    if (n == 1)
    {
        cout << 0 << endl;
        return 0;
    }
    euler(n);
    for (int i = 2; i <= n; ++i)
    {
        len[1] += 1ll * phi[i];
    }
    len[1] = 1ll * n * (n - 1) / 2 - len[1];
    for (int i = 1; i <= n; ++i)
    {
        sum[i] = sum[i - 1] + (vis[i] ^ 1);
    }
    int s = 0;
    for (int i = n; i > n / 2; --i)
    {
        if (!vis[i]) len[0] += n - 1 - (sum[i] - sum[n / 2]);
    } 
    len[0] += n - 1;
    for (int i = 1; i <= n; ++i)
    {
        ++nump[p[i]];
    }
    for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + nump[i];
    for (int i = 2; i <= n; ++i)
    {
        if (2 * p[i] <= n)
        {
            len[3] += sum[n / 2] - sum[n / p[i]];
            if (n / p[i] < p[i] && p[i] <= n / 2)
            {
                len[3] -= nump[p[i]];
            }
        }
    }
    len[3] /= 2;
    len[2] = 1ll * n * (n - 1) / 2 - len[1] - len[3] - len[0];
    cout << 1ll * len[3] * 3 + 1ll * len[2] * 2 + len[1] << endl;
    return 0;
}

$p_{x}p\_x$ 的数量指最小质因数等于 $p_{x}p\_x$ 的数的数量。