2020 多校第九场 E

2020 多校第九场 E https://ac.nowcoder.com/acm/contest/5674/E

给定 $a,b,c,d,x,y$ ，求：

$\prod_{i=a}^{b}\prod_{j=c}^{d}gcd(x^i,y^j)$

TL;DR：找找规律乱搞几下就出来了，WA 到怀疑人生就果断上 $int128$ 。

大家好，我又来丢人了。已经尽我所能地详细写了，希望 ~~我公式没敲错~~ 能帮到大家。

这里假定你能看懂题目的式子并把暴力做法给写出来。当然了暴力是不可能过的，但可以使用暴力模拟一下样例，寻找一些规律。

例如，在模拟样例二的时候，~~显而易见地~~ 可以观察到：

对于 $i=1$ ，只要 $j\geq 2$ ， $gcd(120^i,180^j)=120$ 就一定成立；
同理对于 $i=2$ ，只要 $j\geq 3$ ， $gcd(120^i,180^j)=14400$ 就一定成立；
同理对于 $i=3$ ， $...$ ，不写了不写了自己算几项就有了。

可以猜想到可能会和 $x$ 和 $y$ 的因数有一定的联系，不妨就顺着这个思路探究一下这个恒成立的触发条件到底是什么，从而优化我们的暴力做法。

前置知识：

快速幂 - 就是用 $O(log(n))$ 的时间复杂度算出 $a^n$ 。
算术基本定理 - 任何一个大于 $1$ 的自然数 $N$ ，都可以分解为有限个质数的乘积。
利用算术基本定理计算两个数的最大公因数，这里随便找了一篇文章供参考。

现在我们就利用算术基本定理计算 $gcd(x^i,y^j)$ ，我们首先把 $x$ 和 $y$ 拆分成下面的形式：

$\left\{\begin{matrix} x=\prod_{k=0}^{n}fac[k]^{cnt_x[k]} \\ y=\prod_{k=0}^{n}fac[k]^{cnt_y[k]} \end{matrix}\right.$

其中，对于 $0 \leq k \leq n$ ，有：

$fac[k]$ 是质数；
$cnt_x[k] \geq 0$ ， $cnt_y[k] \geq 0$ ；
$cnt_x[k] + cnt_y[k] > 0$ 。

显然对于任意 $x \geq 2$ 和 $y \geq 2$ ，根据算术基本定理，必定存在符合要求的写法。

那么 $x^i$ 和 $y^j$ 就可以写成下面的形式：

$\left\{\begin{matrix} x^i=\prod_{k=0}^{n}fac[k]^{i \cdot cnt_x[k]} \\ y^j=\prod_{k=0}^{n}fac[k]^{j \cdot cnt_y[k]} \end{matrix}\right.$

不难得到下面的式子：

$gcd(x^i,y^j)=\prod_{k=0}^{n}fac[k]^{min(i \cdot cnt_x[k],j \cdot cnt_y[k])}$

如果看公式难以理解，这里举个栗子，假设要你计算 $gcd(7260^3,2800^4)$ ：

因为有：

$\left\{\begin{matrix} 7260=2^2 \times 3^1 \times 5^1 \times 7^0 \times 11^2 \\ 2800=2^4 \times 3^0 \times 5^2 \times 7^1 \times 11^0 \end{matrix}\right.$

所以有：

$\left\{\begin{matrix} 7260^3=2^6 \times 3^3 \times 5^3 \times 7^0 \times 11^6 \\ 2800^4=2^{16} \times 3^0 \times 5^8 \times 7^4 \times 11^0 \end{matrix}\right.$

那么就可以算出结果：

$gcd(7260^3,2800^4)=2^{min(6,16)} \times 3^{min(3,0)} \times 5^{min(3,8)} \times 7^{min(0,4)} \times 11^{min(6,0)}=2^6 \times 5^3=8000$

现在我们可以把刚刚得出的式子代入到题目里：

$\prod_{i=a}^{b}\prod_{j=c}^{d}gcd(x^i,y^j)=\prod_{i=a}^{b}\prod_{j=c}^{d}\prod_{k=0}^{n}fac[k]^{min(i \cdot cnt_x[k],j \cdot cnt_y[k])}$

然后做一些等价转换，目的是在式子中找到我们接下来需要关注的部分。

首先，根据乘法交换律：

$\prod_{i=a}^{b}\prod_{j=c}^{d}\prod_{k=0}^{n}fac[k]^{min(i \cdot cnt_x[k],j \cdot cnt_y[k])}=\prod_{k=0}^{n}\prod_{i=a}^{b}\prod_{j=c}^{d}fac[k]^{min(i \cdot cnt_x[k],j \cdot cnt_y[k])}$

实际上就是先枚举 $fac$ ，然后再枚举 $i$ 和 $j$ 。

接下来，根据同底数幂相乘，底数不变指数相加：

$\prod_{k=0}^{n}\prod_{i=a}^{b}\prod_{j=c}^{d}fac[k]^{min(i \cdot cnt_x[k],j \cdot cnt_y[k])}=\prod_{k=0}^{n}fac[k]^{\sum_{i=a}^{b}\sum_{j=c}^{d}min(i \cdot cnt_x[k],j \cdot cnt_y[k])}$

我们在这里停一下，尝试口胡一下现在我们应该怎样计算这个式子：

首先对 $x$ 和 $y$ 进行质因数分解，并根据分解结果初始化 $fac$ 、 $cnt_x$ 和 $cnt_y$ 三个数组。要注意这些数组都不会再被更新了，也意味着对于每一个 $fac[k]$ ， $cnt_x[k]$ 和 $cnt_y[k]$ 都是确定的值。然后对于每一个 $fac[k]$ ，我们枚举 $i$ ，然后计算：

$\sum_{j=c}^{d}min(i \cdot cnt_x[k],j \cdot cnt_y[k])$

这一部分就是我们接下来要关注的部分，这是因为：

$min(i \cdot cnt_x[k],j \cdot cnt_y[k])=\left\{\begin{matrix} i \cdot cnt_x[k], \ j > \frac{cnt_x[k]}{cnt_y[k]} i \\ j \cdot cnt_y[k] , \ j \leq \frac{cnt_x[k]}{cnt_y[k]} i \end{matrix}\right.$

这是一个关于 $j$ 的分段函数，而且其中一段是常函数，另一段是一次函数，这意味着我们可以往分段求和的方向想。

考虑临界值的位置：

$edge=\left \lfloor \frac{cnt_x[k]}{cnt_y[k]} i \right \rfloor$

第一种情况： $edge \leq c-1$ ，那么有：

$\sum_{j=c}^{d}min(i \cdot cnt_x[k],j \cdot cnt_y[k])=\sum_{j=c}^{d}(i \cdot cnt_x[k])=(d-c+1)(i \cdot cnt_x[k])$

第二种情况： $c \leq edge \leq d-1$ ，那么有：

$\sum_{j=c}^{d}min(i \cdot cnt_x[k],j \cdot cnt_y[k])=\sum_{j=c}^{edge}(j \cdot cnt_y[k])+\sum_{j=edge+1}^{d}(i \cdot cnt_x[k])=\frac{(c+edge)(edge-c+1)}{2}cnt_y[k]+(d-edge)(i \cdot cnt_x[k])$

第三种情况： $edge \geq d$ ，那么有：

$\sum_{j=c}^{d}min(i \cdot cnt_x[k],j \cdot cnt_y[k])=\sum_{j=c}^{d}(j \cdot cnt_y[k])=\frac{(c+d)(d-c+1)}{2}cnt_y[k]$

如果还是对求和过程有疑问，其实这就是等差数列求和嘛！首项加末项乘以项数除以二。

当然在编程的时候可能希望把三种情况归类成一种情况，是可以的：

直接将边界调整到 $[c-1,d]$ 范围内：

$edge=min(d, max(c - 1, \left \lfloor \frac{cnt_x[k]}{cnt_y[k]} i \right \rfloor))$

然后套用第二种情况的式子，你会发现将边界值调整后，这个式子同样适用于情况一和情况三。

$\sum_{j=c}^{d}min(i \cdot cnt_x[k],j \cdot cnt_y[k])=\frac{(c+edge)(edge-c+1)}{2}cnt_y[k]+(d-edge)(i \cdot cnt_x[k])$

复杂度足够应付这个数据范围了，那就到此为止。

接下来就是编程实现，刚才已经口胡过做法了（请看上面的粗体字）。有几个地方可能需要考虑的：

$x=1$ 或 $y=1$ ，无论 $a,b,c,d$ 是什么，很显然答案必定是 $1$ ，其实可以不特判的。
$cnt_y[k]=0$ ，在计算边界值 $edge$ 的时候不考虑这个可能会有除零错误，但是很显然这种情况下 $fac[k]$ 不会影响答案。
数据范围，掐指一算可能会爆 $long \ long$ ，那就使劲开 $int128$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;

ll a, b, c, d, x, y;
map<ll, pair<ll, ll>> fac;

ll qpow(ll a, __int128 b)
{
    ll ans = 1, base = a;
    while (b)
    {
        if (b & 1)
            ans = ans * base % MOD;
        base = base * base % MOD;
        b >>= 1;
    }
    return ans;
}

void update_factor(ll x, bool loc)
{
    ll temp_x = x;
    for (ll i = 2; i * i <= x; i++)
    {
        while (temp_x % i == 0)
        {
            loc == 0 ? fac[i].first++ : fac[i].second++;
            temp_x /= i;
        }
    }
    if (temp_x != 1)
    {
        loc == 0 ? fac[temp_x].first++ : fac[temp_x].second++;
    }
}

int main()
{
    cin >> a >> b >> c >> d >> x >> y;
    update_factor(x, 0);
    update_factor(y, 1);
    ll ans = 1;
    for (auto k : fac)
    {
        if (k.second.second == 0)
        {
            continue;
        }
        __int128 curcnt = 0;
        for (int i = a; i <= b; i++)
        {
            ll edge = k.second.first * i / k.second.second;
            edge = min(d, max(c - 1, edge));
            curcnt += (d - edge) * k.second.first * i;
            curcnt += k.second.second * (edge + c) * (edge - c + 1) / 2;
        }
        ans = ans * qpow(k.first, curcnt) % MOD;
    }
    cout << ans << endl;
}

大家一起加油鸭！可以随意转载本题解（注明来源），最后附上本文 Markdown 源码。