ACM模版

描述

题解

题意是求

ans=∑i=1n∑j=1m[gcd(i,j) is prime]

很明显是莫比乌斯反演的问题，首先我们设

f(d)=∑i=1n∑j=1m[gcd(i,j)=d]
所以
ans=∑d is primef(d)
接着我们设
g(d)=∑i=1n∑j=1m[d|gcd(i,j)]
可以进一步转换为
g(d)=⌊nd⌋∗⌊md⌋
所以
f(d)=∑i=1⌊nd⌋g(d∗i)∗μ(i)
继而
ans=∑d is prime∑i=1⌊nd⌋⌊nd∗i⌋∗⌊md∗i⌋∗μ(i)
设
t=d∗i
最终可以化为
ans=∑t=1n⌊nt⌋∗⌊mt⌋∗∑d|t,d is primeμ(td)

最后问题也就变成了一个和 t <script type="math/tex" id="MathJax-Element-1578">t</script> 有关的公式了，我们只需要预处理一下，然后分块儿搞就好了。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 5e6 + 10;

ll ans;
int n, m;
ll a[MAXN];
int pri[MAXN];
int miu[MAXN];
bool bz[MAXN];

void init()
{
    miu[1] = 1;
    for (int i = 2; i < MAXN; i++)
    {
        if (!bz[i])
        {
            pri[++pri[0]] = i;
            miu[i] = -1;
        }
        for (int j = 1; j <= pri[0]; j++)
        {
            int k = i * pri[j];
            if (k > MAXN)
            {
                break;
            }

            bz[k] = 1;
            if (!(i % pri[j]))
            {
                break;
            }

            miu[k] = -miu[i];
        }
    }

    for (int i = 1; i <= pri[0]; i++)
    {
        int tmp = MAXN / pri[i];
        for (int j = 1; j <= tmp; j++)
        {
            a[pri[i] * j] += miu[j];
        }
    }
    for (int i = 1; i < MAXN; i++)
    {
        a[i] += a[i - 1];
    }
}

int main()
{
    init();

    int T;
    scanf("%d", &T);

    while (T--)
    {
        scanf("%d%d", &n, &m);

        ans = 0;
        if (n > m)
        {
            swap(n, m);
        }
        for (int l = 1, r; l <= n; l = r + 1)
        {
            r = min(n / (n / l), m / (m / l));
            ll sum = (ll)(n / l) * (m / l);
            ans += sum * (a[r] - a[l - 1]);
        }

        printf("%lld\n", ans);
    }

    return 0;
}