[洛谷P2257]YY的GCD

题目大意：多组数据（小于等于$10000$），每组数据给你$n,m(1\leqslant n,m\leqslant 10^7)$，求$\displaystyle\sum\limits_{x=1}^n\displaystyle\sum\limits_{y=1}^m[(x,y)\in \rm prime]$（$(a,b)$为$a,b$的$gcd$）

题解：$下文中令n\leqslant m$

$$
莫比乌斯反演公式：\\
\def\dsum{\displaystyle\sum\limits}\\
1.F(x)=\dsum_{d|x}f(d)\Rightarrow f(x)=\dsum_{d|x}\mu\Big(\dfrac{x}{d}\Big)F(d)\\
2.F(x)=\dsum_{x|d}f(d)\Rightarrow f(x)=\dsum_{x|d}\mu\Big(\dfrac{d}{x}\Big)F(d)\\
$$

$$
\begin{align*}
\def\dsum{\displaystyle\sum\limits}
令f(p)&=\dsum_{i=1}^n\dsum_{j=1}^m[(i,j)==p]\\
令F(p)&=\dsum_{p|k}f(k)\\
    &=\dsum_{p|k}\dsum_{i=1}^n\dsum_{j=1}^m[(i,j)==k]\\
    &=\dsum_{i=1}^n\dsum_{j=1}^m[p|(i,j)]\\
    &=\left\lfloor\dfrac{n}{p}\right\rfloor \cdot \left\lfloor\dfrac{m}{p}\right\rfloor\\
通过反演公式&(2):\\
\therefore f(p)&=\dsum_{p|k}F(k)\mu\Big(\dfrac{k}{p}\Big)\\
            &=\dsum_{i=1}^n\mu(i)\left\lfloor\dfrac{n}{i\cdot p}\right\rfloor\cdot\left\lfloor\dfrac{m}{i\cdot p}\right\rfloor\\
            
\therefore ans&=\dsum_{p\in \rm prime}f(p)\\
            &=\dsum_{p\in \rm prime}\dsum_{i=1}^n\mu(i)\left\lfloor\dfrac{n}{i\cdot p}\right\rfloor\cdot\left\lfloor\dfrac{m}{i\cdot p}\right\rfloor\\
            &=\dsum_{i=1}^n\dsum_{p\in \rm prime\\p|i}\mu\Big(\dfrac{i}{p}\Big)\left\lfloor\dfrac{n}{i}\right\rfloor\cdot\left\lfloor\dfrac{m}{i}\right\rfloor\\
令g(p)&=\dsum_{p\in \rm prime\\p|i}\mu\Big(\dfrac{i}{p}\Big)（可以预处理）\\
\therefore ans&=\dsum_{i=1}^n g(i)\left\lfloor\dfrac{n}{i}\right\rfloor\cdot\left\lfloor\dfrac{m}{i}\right\rfloor\\
\end{align*}\\
然而这样还是会TLE,可以令sg(p)=\dsum_{i=1}^p g(i),然后就可以一次性求出\left\lfloor\dfrac{n}{i}\right\rfloor\cdot\left\lfloor\dfrac{m}{i}\right\rfloor相同的区间就行了
$$

卡点：1.没有前缀和优化导致$TLE$



C++ Code：

#include <cstdio>
#include <cstring>
#define maxn 10000010
using namespace std;
int Tim, n, m;
int miu[maxn], plist[maxn], ptot;
int g[maxn];
bool isp[maxn];
void sieve(int n) {
    memset(isp, true, sizeof isp);
    miu[1] = 1;
    for (int i = 2; i < n; i++) {
        if (isp[i]) plist[ptot++] = i, miu[i] = -1;
        for (int j = 0; j < ptot && i * plist[j] < n; j++) {
            int tmp = i * plist[j];
            isp[tmp] = false;
            if (i % plist[j] == 0) {
                miu[tmp] = 0;
                break;
            }
            miu[tmp] = -miu[i];
        }
    }
    for (int i = 0; i < ptot; i++) {
        for (int j  = 1; j * plist[i] < n; j++)
            g[j * plist[i]] += miu[j];
    }
    for (int i = 2; i <= n; i++) g[i] += g[i - 1];
}
inline int min(int a, int b) {return a < b ? a : b;}
long long solve(int n, int m) {
    long long ans = 0;
    int i, j;
    int tmp = min(n, m);
    for (i = 1; i <= tmp; i = j + 1) {
        j = min(n / (n / i), m / (m / i));
        ans += 1ll * (n / i) * (m / i) * (g[j] - g[i - 1]);
    }
    return ans;
}
int main() {
    sieve(maxn);
    scanf("%d", &Tim);
    while (Tim --> 0) {
        scanf("%d%d", &n, &m);
        printf("%lld\n", solve(n, m));
    }
    return 0;
}

[洛谷P2257]YY的GCD

原文：https://www.cnblogs.com/Memory-of-winter/p/9516992.html