题意
给出 a, b, c, d, x, y,让求出 (prod_{i=a}^{b}prod_{i=c}^{d}gcd(x^i,y^j)\%mod)
思路
先求出 (x), (y) 的 gcd，进行质因子分解，然后第一层 for 循环枚举质因子，第二层 for 循环枚举 (i)。
对于质因子 (p) 和 (i)，假设 (p) 在 (x) 中出现了 (xp) 次，在 (y) 中出现了 (yp) 次，我们可以求出一个分界线 (mid)。
使得当 (jleq mid) 时，(x^i) 中 (p) 的出现次数大于等于 (y^{j}) 中 (p) 的出现次数，即 (xp imes i geq yp imes j) ；当 (jgeq mid) 时， (x^i) 中 (p) 的出现次数小于等于(y^{j}) 中 (p) 的出现次数；
那么根据 gcd ，当 (jleq mid) 的时候，p 对答案的贡献的幂次为 (y^j) 中 (p) 的出现次数，即 (yp imes j)，当 (jgeq mid) 时，(p) 对答案的贡献幂次为 (x^i) 的质因子中 (p) 的出现次数，即(xp imes i)。
-
(j leq mid) 时贡献的幂次为
if mid >= c: mid = min(mid,d) num = (c + mid) * (num - c + 1) / 2 * yp -
(j geq mid) 时贡献的幂次为
if mid <= d: mid = max(mid, c - 1) num = (d - mid ) * xp
注意：对于每个 i 求出来 p 的贡献幂次之后，不要直接使用快速幂计算，把所有 i 中 p 的贡献幂次累加起来，最后进行快速幂，否则会超时，幂次和使用__int128
代码
#include <bits/stdc++.h>
#define fuck system("pause")
#define emplace_back push_back
#define pb push_back
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const double eps = 1e-6;
const ll inf = 0x3f3f3f3f;
const ll N = 2e5 + 10;
ll tot, vec[N];
void find_fat(ll val)
{
tot = 0;
for (ll i = 2; i * i <= val; i++) {
if (val % i == 0) {
vec[++tot] = i;
}
while (val % i == 0)
val /= i;
}
if (val > 1)
vec[++tot] = val;
}
ll qpow(ll a, __int128 b)
{
ll ans = 1;
while (b) {
if (b & 1) {
ans = (ans * a) % mod;
}
b >>= 1;
a = a * a % mod;
}
return ans % mod;
}
int main()
{
ll a, b, x, y, c, d;
scanf("%lld%lld%lld%lld%lld%lld", &a, &b, &c, &d, &x, &y);
ll gcd = __gcd(x, y);
find_fat(gcd);
ll ans = 1, xp = 0, yp = 0, p, tmp;
for (ll j = 1; j <= tot; j++) {//枚举质因子
p = vec[j], tmp = x;
xp = yp = 0;
while (tmp % p == 0) {
xp++;
tmp /= p;
}
tmp = y;
while (tmp % p == 0) {
yp++;
tmp /= p;
}
__int128 sum = 0;
for (ll i = a; i <= b; i++) {
ll r = yp, l = xp * i;
ll num = l / r;
if (num >= c) {
ll maxn = min(num, d);
sum+=(c + maxn) * (maxn - c + 1) / 2 * r;
}
if (num <= d) {
ll minn = max(num, c - 1);
sum += (d - minn) * l;
}
}
ans = (ans * qpow(p, sum)) % mod;
}
printf("%lld
", ans);
return 0;
}
/*
1 3000000 1 3000000 500000000 500000000
*/