E Groundhog Chasing Death（2020牛客暑期多校訓練營（第九場））（思維+費馬小定理+素數）

鏈接：https://ac.nowcoder.com/acm/contest/5674/E
來源：牛客網

時間限制：C/C++ 2秒，其他語言4秒
空間限制：C/C++ 262144K，其他語言524288K
64bit IO Format: %lld

題目描述

As we all know,「Groundhog chasing death」 means 「GCD」,while 「GCD」 stands for 「greatest common divisor」.

So you need to calculate $\displaystyle\prod_{i=a}^b\prod_{j=c}^d\gcd(x^i,y^j)$ modulo ${998244353}$.

輸入描述:

One line which contains six intergers ${a,b,c,d,x,y}$.

輸出描述:

One line which contains
$\displaystyle\prod_{i=a}^b\prod_{j=c}^d\gcd(x^i,y^j)$ modulo ${998244353}$.

範例1

輸入

1 2 1 2 8 4

輸出

2048

範例2

輸入

1 2 3 4 120 180

輸出

235140177

備註:

$0\leqslant{a,b,c,d\leqslant 3\times10^6,0<x,y\leqslant10^9},a\leqslant b,c\leqslant d$.

題意

給出 $a,b,c,d,x,y$，讓求出 $\displaystyle\prod_{i=a}^b\prod_{j=c}^d\gcd(x^i,y^j)$。

題解

暴力做法：列舉$i$和$j$，算出$x^i$和$y^j$求乘積。注意求冪的時候不能取模，因爲取模後最大公約數就變了。時間複雜度$O(n^2logn)$，既會爆long long，又會超時。

改進做法：考慮$x$和$y$的公共素因子，取$i$次方和$j$次方就相當於把素因子的個數變爲$i$倍或$j$倍。這樣的話每次列舉時更新因子個數，列舉結束後再把各個素因子乘起來，乘的時候可以取模。時間複雜度$O(n^2logn)$。會超時但不會爆long long了。

繼續改進：考慮到列舉過程中$x$和$y$的值是不變的，所以預處理出$x$和$y$的公共素因子，並求出每個素因子分別在$x$和$y$中出現的次數，那麼$x^i$就相當於把x中的素因子個數都變成$i$倍，$y^j$同理。

把$x$和$y$中每個素因子的個數分開考慮，因爲題目要求的是求所有gcd的乘積，所以我們把用於構建gcd的素因子的個數直接加起來即可。

發現每列舉一個$i$，對應的連續的$j$存線上性關係：當$j$比較小的時候，$x^i$和$y^j$的最大公約數的限制主要體現在$y$的素因子個數上。$j$不斷增加，$y$中的素因子個數就變成了一個個等差數列。可以利用等差數列求和公式$O(1)$算出這一段區間的$j$對$y$的素因子個數的貢獻，而當$y$比較大時，gcd的限制主要體現在$x$的素因子個數上，那麼不論$j$再怎麼增加，$i$不變，那麼構建出來的gcd的值就不會變，此時後一半區間的$y$對素因子的貢獻就是$x$中素因子出現的個數乘以這一段$y$的區間長度。

注意列舉的時候不要直接計算出素因子的冪，不然會超時。先儲存每個素因子的總個數，之後再求冪和乘積。注意直接儲存素因子的總個數會爆long long。需要利用費馬小定理：$a^{(p-1)}≡1(mod\ p)$，把素因子的個數對「mod-1」取模即可。時間複雜度$O(n\ log n)$

最後利用快速冪算出每個冪的值，然後求乘積即可。

程式碼

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define _for(i, a) for(register int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for(register int i = (a), lennn = (b); i <= lennn; ++i)
#define scl(x) scanf("%lld", &x)
using namespace std;
typedef long long LL;
const int mod = 998244353;
int debug = 0;

LL a, b, c, d, x, y;
vector<LL> gcdd, gnumx, gnumy, mi;  //gcdd儲存x和y的公共素因子，gnumx儲存x中每個公共素因子的個數，gnumy儲存y中每個公共素因子的個數，mi儲存最終答案中每個公共素因子的個數。

inline void init() {
    gcdd.clear();
    gnumx.clear();
    gnumy.clear();
    mi.clear();
}

struct Prime {
    vector<int> arr;
    int vis[100006];
    void doit(int maxnum) {
        for(int i = 2; i <= maxnum; ++i) {
            if(!vis[i]) arr.push_back(i);
            for(int j = 0; j < arr.size() && arr[j] * i <= maxnum; ++j) {
                vis[arr[j] * i] = 1;
                if(i % arr[j] == 0) break;
            }
        }
    }
}P;

inline LL quickPow(LL x, LL n) {
    LL ans = 1;
    while(n) {
        if(n & 1) ans *= x, ans %= mod;
        x *= x, x %= mod;
        n >>= 1;
    }
    return ans;
}

inline void sol() {
    init();
    LL g = __gcd(x, y);
    for(int i = 0; P.arr[i] * P.arr[i] <= g; ++i) { //把x和y的最大公約數分解，把素因子存起來
        if(g % P.arr[i] == 0) {
            gcdd.push_back(P.arr[i]);
            while(g % P.arr[i] == 0) g /= P.arr[i];
        }
    }
    if(g > 1) gcdd.push_back(g);
    mi.resize(gcdd.size());
    fill(mi.begin(), mi.end(), 0);
    LL tx = x, ty = y;
    for(auto &i : gcdd) {       //求出每個素因子在x和y中出現的次數
        gnumx.push_back(0);
        while(tx % i == 0) {
            ++gnumx.back();
            tx /= i;
        }
        gnumy.push_back(0);
        while(ty % i == 0) {
            ++gnumy.back();
            ty /= i;
        }
    }
    if(debug) {
        _for(i, gcdd.size()) {
            printf("%d: x %d, y %d\n", gcdd[i], gnumx[i], gnumy[i]);
        }
    }
    LL ans = 1;
    _rep(i, a, b) {             //列舉每一個i，計算j的貢獻
        _for(x, gcdd.size()) {
            LL numx = 0;
            LL num = gnumx[x] * i;
            LL m = num / gnumy[x];
            if(m >= c) {        //gcd的值主要被y的素因子個數所限制，等差數列求和
                LL r = min(m, d);
                numx += gnumy[x] * (r + c) * (r - c + 1) / 2;
            }
            if(d > m) {         //gcd的值主要被x的素因子個數所限制，此時j的貢獻是一段恆定的值
                LL l = max(m + 1, c);
                numx += num * (d - l + 1);
            }
            mi[x] += numx;
            mi[x] %= (mod - 1);//費馬小定理
        }
    }
    _for(i, gcdd.size()) {
        ans = ans * quickPow(gcdd[i], mi[i]) % mod;
    }
    printf("%lld\n", ans);
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
    debug = 1;
#endif
    time_t beg, end;
    if(debug) beg = clock();

    P.doit(100000);
    while(~scl(a)) {
        scl(b), scl(c), scl(d), scl(x), scl(y);
        sol();
    }

    if(debug) {
        end = clock();
        printf("time:%.2fs\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
    }
    return 0;
}

/*
in:
0 3000000 0 3000000
223092870
223092870

out:
824590783

*/