E Groundhog Chasing Death（2020牛客暑期多校训练营（第九场））（思维+费马小定理+素数）_综合

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

输出

示例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
#elsefreopen("in.txt", "r", stdin);debug = 1;
#endiftime_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 223092870out: 824590783*/