简单的GCD问题整理

这两天做了好几个GCD的题目，思路都类似，所以来整理一下。

P2568 GCD

先看第一个 GCD ：给定整数 $ N $，求 $ 1\le x,y \le N $ 且 $ GCD(x,y) $ 为素数的数对 $ (x,y) $ 有多少对。$ (1\le N\le 10^7) $

由于只有一组数据，我们可以用以前求GCD SUM的方式去做：GCD SUM

P2303 [SDOI2012]Longge的问题

再看第二个 Longge的问题：求 $ \sum\limits_{i=1}^N \gcd(i, N)$ $(1≤N≤2^{32})$

一看数据范围这么大，$qwq$，化简化简呗。

化简的思路：

一个个求gcd可以变成枚举$gcd=j$，求$gcd(i,N)=j$的个数，然后$j×[gcd(i,N)==j]$
求$gcd(i,N)=j$ 可以等价于$gcd(i/j,N/j)=1$

根据思路进行化简：

$\sum\limits_{i=1}^N\gcd(i,N)=\sum\limits_{j=1}^Nj×\sum\limits_{i=1}^N[gcd(i,N)==j]$

$=\sum\limits_{j=1,j|N}^Nj\times\sum\limits_{i=1}^N[gcd(i/j,N/j)==1]$

然后 $ \sum\limits_{j=1,j|N}^N j $ 不就是在枚举 $N$ 的因子么，$\sum\limits_{i=1}^N[gcd(i/j,N/j)==1]$ 不就是 $\phi(N/j)$ 么。

所以原式 $=\sum\limits_{j=1,j|N}^Nj\times\phi(N/j)$

因为数据太大了，没法上来把$\phi(i)$都筛出来，不过我们可以在$\sqrt{i}$的复杂度内把$\phi(i)$算出来，所以可以先$\sqrt{N}$复杂度去枚举$N$的因子，然后再$\sqrt{i}$复杂度算$\phi$，最后复杂度为 $O($ 能过 $)$

UVA11424 GCD-Extreme(I)

再看第三个 UVA11424 GCD-Extreme(I) ：求 $\sum\limits_{i=1}^{N-1}\sum\limits_{j=i+1}^Ngcd(i,j)$ $(2\le N\le 200000)$

要不是这个题有20000组数据，就可以和GCD SUM 一个做法了。现在我们要想一个复杂度更优的做法。

来，看如果我们把两个$\sum$交换一下位置会是怎么样的：$\sum\limits_{j=2}^N\sum\limits_{i=1}^{N-1}gcd(i,j)$

是不是很眼熟，$qwq$ 跟上一题是不是差不多，只不过上一题$j=N$，这一次$j$从$2$到$N$都得枚举一遍,但是这次数据范围也小啊，可以支持我们先把 $\phi$ 筛出来，然后暴力枚举$j$，然后$\sqrt{j}$枚举$j$的因子。

$20000$组数据怎么办？其实排个序从小到大一个个算就可以了，很明显这个式子$\sum\limits_{j=1,j|N}^Nj\times\phi(N/j)$ 你多组数据，按大小排序，假设你$N=x$已经算完了，那$N=x+1$不就直接加个枚举$x+1$的因子的$for$循环算一遍就可以了，不用从头开始算。

SP3871 GCDEX-GCD Extreme

UVA11426 GCD-Extreme(II)

再看第四、五个 SP3871 GCDEX-GCD Extreme UVA11426 GCD-Extreme(II)

这两个题和上面第三个题的区别就是数据范围大了点，如果我们暴力枚举$j$，然后$\sqrt{j}$枚举$j$的因子的话，明显会$TLE$，也就是说我们枚举因子的方法太暴力了，需要改进。

正着枚举暴力，我们可以反过来啊，就像求$\sum\sum\gcd(i,j)$可以变成$\sum\ k\times\sum\sum[gcd(i,j)==k]$一样。

我们可以直接枚举一个数$i$，然后把因子里面有i的数都更新一遍。

1 2	for (int i = 1; i <= sqrt(n); i++) if (!(n % i)) //这样子枚举太慢 for (int i = 1; i <= n; i++) for (int j = 2 * i; j <= n; j += i) //这样子就快了

这些题可以选择先把答案都预处理出来，然后$O(1)$输出：

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MaxN = 4000001;
const int Maxn = 20010;

int n, cnt = 0;
int prime[MaxN + 10];
ll phi[MaxN + 10];
int Not_p[MaxN + 10];
ll Ans[MaxN + 10];

inline int read()
{
    int fl = 1, rt = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            fl = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        rt = rt * 10 + ch - '0';
        ch = getchar();
    }
    return fl * rt;
}

void Prime_Ini()
{
    Not_p[1] = 1;
    phi[1] = 1ll;
    for (int i = 1; i <= MaxN; i++)
    {
        if (!Not_p[i])
            prime[++cnt] = i, phi[i] = i - 1;
        for (int j = 1; j <= cnt; j++)
        {
            if (i * prime[j] > MaxN)
                break;
            Not_p[i * prime[j]] = 1;
            phi[i * prime[j]] = phi[i] * phi[prime[j]];
            if (!(i % prime[j]))
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
    for (int x = 1; x <= MaxN; x++)
    {
        for (int j = x * 2; j <= MaxN; j += x)
            Ans[j] += (ll)x * phi[j / x];
    }
    for (int i = 2; i <= MaxN; i++)
        Ans[i] += Ans[i - 1];
}

void Solve()
{
    Prime_Ini();
    n = read();
    while (n)
    {
        printf("%lld\n", Ans[n]);
        n = read();
    }
}

int main()
{
    Solve();

    return 0;
}