第45届ICPC亚洲区域赛（济南）的F题，链接。强烈建议一做。

Solution

        题意很明确，给定数列$A,B$，求$C$，使得：

        首先枚举这两个$gcd$，只需要枚举$k$的因子即可：

        即为：

        把这个$gcd=1$用莫比乌斯反演处理掉，只需要枚举一步$\frac {k}{d_1}$和$\frac{k}{d_2}$的因子：

        换元，令$D_1=c_1d_1,D_2=c_2d_2$，得到：

        中间是$A,B$与莫比乌斯函数的狄利克雷卷积，先不用管它。重点在后面的$\sum_{i=1}^k[D_1|i][D_2|k+1-i]$。
        首先需要明确$D_1$与$D_2$是互质的。可以使用反证法证明：假设$gcd(D_1,D_2)=d>1$，那么$d|gcd(i,k+1-i)$，即$d|(k+1)$，而$d|k$且$k$与$k+1$互质，故不成立。
        设$i=k_1D_1,k+1-i=k_2D_2$，那么有：

        于是$\sum_{i=1}^k[D_1|i][D_2|k+1-i]$可以看作上面方程的正整数解的数量。
        上面方程等价于同余方程：

        以及：

        由于$D_1$与$D_2$互质，于是上面两个方程都有唯一解，分别设为$x,y$，即：

        能够得到：

        那么：

        令$xD_1+yD_2\equiv D\pmod {D_1D_2}$即为：

        我们证明$D$与$D_1D_2$互质。
假设存在质数$p$满足$p|D$且$p|D_1D_2$，考虑到$D_1$与$D_2$互质，那么有$p|D_1$或者$p|D_2$，不妨假设$p|D_1$。此时根据$xD_1+yD_2\equiv D\pmod {D_1D_2}$，得到$p|yD_2$，从而$p|y$，即$y$和$D_1$不互质。这与$yD_2\equiv 1\pmod {D_1}$矛盾，于是只能$D$与$D_1D_2$互质，证毕。
        那么上式就可以化简为$xD_1+yD_2\equiv D\equiv 1\pmod {D_1D_2}$
        将$x,y$规范到$1\leq x<D_2,1\leq y< D_1$，那么$2\leq xD_1+yD_2<2D_1D_2$。于是只能$xD_1+yD_2=D_1D_2+1$。
        得到这个结论后，剩下的$k-D_1D_2$就可以来补足上式。
        假设$k-D_1D_2=aD_1D_2$，那么在$a=a_1+a_2$时，就可以将$x$加上$a_1D_2$，$y$加上$a_2D_1$来使得$(x+a_1D_2)D_1+(y+a_2D_1)D_2=D_1D_2+1+k-D_1D_2=k+1$得到一组解。很明显有$0\leq a_1\leq a$这$a+1$种情况，而$a=\frac{k}{D_1D_2}-1$，于是解的数量为$\frac{k}{D_1D_2}$。
        这样我们就处理好了$\sum_{i=1}^k[D_1|i][D_2|k+1-i]=\frac{k}{D_1D_2}[gcd(D_1D_2)=1]$，所以原式为：

        为了让这个式子好看一点，化为：

        枚举$D=D_1D_2$得到：

        思路就很明显了，答案就是$id*((A*\mu)\times (B*\mu))$，其中$*$是狄利克雷卷积，$\times$是互质狄利克雷卷积。
        我们可以$O(nlogn)$处理因子，然后在$O(nlogn)$复杂度下完成狄利克雷卷积的操作。这里唯一的难点是互质狄利克雷卷积，可能会写出$O(nlog^2n)$的算法。

关于互质狄利克雷卷积

        如果能$O(1)$判断整数$a$与$b$是否互质，就能在$O(nlogn)$复杂度内完成互质狄利克雷卷积操作。
        至于如何$O(1)$判断，方法有很多，这里使用因子数量法来判断。由于因子数量$\sigma$是一个积性函数，我们可以通过$\sigma(ab)=\sigma(a)\sigma(b)$是否成立来判断两者是否互质。当然还可以使用欧拉函数之类的方法来快速判断。
        很容易证明使用$\sigma$是成立的。首先$a$和$b$互质时，明显有$\sigma(ab)=\sigma(a)\sigma(b)$成立。而假设存在质数$p$使得$p|gcd(a,b)$，根据因子数量的计算公式，设$ab$的$p$因子质数为$n$，且$a$和$b$的$p$因子指数为$x,y$，那么$\sigma(a)\sigma(b)$中会出现$(x+1)(y+1)$这一项，而$\sigma(ab)$中会出现$(n+1)=(a+b+1)$这一项，由于$p|gcd(a,b)$，故$ab\geq 1$，即$(a+b+1)<(a+1)(b+1)$，于是必然有$\sigma(ab)<\sigma(a)\sigma(b)$。
        $\sigma$可以通过线性筛在$O(n)$复杂度内求出来，可以参考这篇文章。

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
const int N = 500000 + 5, mod = 998244353;
typedef long long ll;
vector<int> vec[N];
int mu[N], pr[N], tot, bk[N], a[N], b[N], n, c[N], aa[N], bb[N], cp[N], sig[N], num[N];
int main()
{
    sig[1] = mu[1] = 1;
    for (int i = 2; i <= 500000; i++) {
        if (!bk[i]) pr[++tot] = i, mu[i] = -1, sig[i] = 2, num[i] = 1;
        for (int j = 1; j <= tot; j++) {
            if (1ll * pr[j] * i > 500000) break;
            bk[pr[j] * i] = 1;
            if (i % pr[j] == 0) {
                sig[i * pr[j]] = sig[num[i * pr[j]] = num[i]] + sig[i];
                break;
            }
            mu[pr[j] * i] = -mu[i], sig[i * pr[j]] = sig[i] * 2, num[i * pr[j]] = i;
        }
    }
    for (int i = 1; i <= 500000; i++) {
        for (int j = i; j <= 500000; j += i) vec[j].push_back(i);
    }
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i <= n; i++) scanf("%d", b + i);
    for (int i = 1; i <= n; i++) {
        for (int s : vec[i]) aa[i] = (aa[i] + 1ll * a[s] * mu[i / s] % mod) % mod;
    }
    for (int i = 1; i <= n; i++) {
        for (int s : vec[i]) bb[i] = (bb[i] + 1ll * b[s] * mu[i / s] % mod) % mod;
    }
    for (int i = 1; i <= n; i++) {
        for (int s : vec[i]) {
            if (sig[s] * sig[i / s] == sig[i]) cp[i] = (cp[i] + 1ll * aa[s] * bb[i / s] % mod) % mod;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int s : vec[i]) c[i] = (c[i] + 1ll * s * cp[i / s] % mod) % mod;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans ^= ((c[i] + mod) % mod);
    printf("%d", ans);
    return 0;
}