2020牛客暑期多校训练营Groundhog Chasing Death(质因数分解，费马小定理，模拟)

Groundhog Chasing Death

题目描述

样例

input:
1 2 1 2 8 4
output:
2048
input:
1 2 3 4 120 180
output:
235140177

题目大意

给定$a,b,c,d,x,y$a,b,c,d,x,y，求：
$\mathop{\prod}\limits_{i=a}^{b}\mathop{\prod}\limits_{j=c}^{d}\gcd(x^i,y^j)$i=a∏b​j=c∏d​gcd(xi,yj)

分析

首先我们考虑对于$\gcd(x,y)$gcd(x,y)的值是多少。嗯，是它们质因数分解之后的公共部分。那么对于一个数的幂次之后，其质因子的变化是乘上了这个指数。所以，看到数据范围是不可能暴力的，要从这一方面入手。

那么数据范围是允许$O(n\log n)$O(nlogn)的，所以可以分解质因数，然后对于每个质因数都单独考虑，由于对别的质因数都没有干扰，所以可以放心地去搞这个。

假设我们分解：
$x=p_1^{a_1}*p_2^{a_2}\dots p_n^{a_n}$x=p1a1​​∗p2a2​​…pnan​​
$y=q_1^{b_1}*q_2^{b_2}\dots q_m^{b_m}$y=q1b1​​∗q2b2​​…qmbm​​
不妨我们假设其中有质数$p$p是$x,y$x,y共同的因子，那么除一下，看有多少能除出来。
假设$x$x中有$aa$aa个，$y$y中有$bb$bb个。
那么答案应该乘上：
$p^{\mathop{\sum}\limits_{i=a}^{b}\mathop{\sum}\limits_{j=c}^{b}\min(aa*i,bb*j)}$pi=a∑b​j=c∑b​min(aa∗i,bb∗j)
这个还是比较好理解的，因为我当前是考虑这个质因子在所有公因数中乘了多少次，那么公共部分就是$\min(aa*i,bb*j)$min(aa∗i,bb∗j)，然后在底数中是连乘，那么在指数中就是连加了。

但是一拍脑瓜发现，这还是会超时，反而比原来的算法更加劣了。那么就要用到：当题目给了多种变量的时候，不妨固定其中的一个，然后尝试将另一个优化，之后枚举固定的一个就可以了。

这里，我们不妨固定$i$i，那么对于一个固定的$i$i，$i*aa$i∗aa也就固定了，那么对于$\min()$min()我就可以分成两个阶段，第一个是$j*bb<i*aa$j∗bb<i∗aa，那么这个是一个随着$j$j增长的一个等差数列，可以直接求和，第二个更加简单，直接就是$i*aa<j*bb$i∗aa<j∗bb，那么这段区间内的和就是$i*aa$i∗aa乘上区间长度了。
那么这个区间很好求了，分割点就是假设$i*aa=j*bb$i∗aa=j∗bb那么
$j=i*aa/bb$j=i∗aa/bb
这里要注意的是，分割点可能不落在$c,d$c,d之间，因此如果比$c$c还小，那么只有$i*aa$i∗aa了，如果比$d$d还大，那么就是全部都是等差数列了。所以这里需要特判一下。

还有一个问题，你这个指数加起来可能爆了long long啊，那怎么搞。(小声bb__int128)，根据题目中给了一个模数，很多人就想到模这个数，但是显然，这是在指数中的，不能模成外面的数，那么怎么搞？
此时打开数论的宝库，掏出费马小定理。显然998244353是素数。
$a^{p-1}\equiv 1 (mod\,p)$ap−1≡1(modp)
显然，其值是以$p-1$p−1一个循环又回到1的，所以，指数应该模$p-1$p−1

如果你是枚举因数，是不可能到1e9的级别的，所以最后除出来可能不为1，那么此时$x$x本身就是一个大素数，要判断。
接下来就是代码。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+10;
const int MOD=998244353;//p
const int mod=998244352;//p-1
ll ksm(ll a,ll b)
{
	ll ret=1;
	while(b){
		if(b&1) ret=ret*a%MOD;
		a=a*a%MOD,b>>=1;
	}return ret;
}//快速幂
ll a,b,c,d,x,y,ans=1;
void solve(int p)
{//当前枚举的质因子为p
	ll aa=0,bb=0;
	while(x%p==0) aa++,x/=p;//算出各自有多少，即求aa和bb
	while(y%p==0) bb++,y/=p;
	if(aa==0||bb==0) return;//如果不是公共的，那么直接return了
	ll tp=0;
	for(ll i=a;i<=b;i++){
		ll j=aa*i/bb,tmp,now;
		if(j<c){
			tmp=(d-c+1)*i%mod*aa%mod;
		}//小于c，那么全是i*aa
		else if(j>=d){
			tmp=(c+d)*(d-c+1)/2%mod*bb%mod;
		}//大于d，那么全是等差数列
		else{
			now=(c+j)*(j-c+1)/2%mod*bb%mod;
			tmp=(now+(d-j)*i%mod*aa%mod)%mod;
		}//否则分段考虑，O(1)解决
		tp=(tp+tmp)%mod;
	}
	ans=1ll*ans*ksm(p,tp)%MOD;
}
int main()
{
	scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&d,&x,&y);
	for(int k=2;k<=x;k++){
		if(x%k==0) solve(k);
	}//这是我看到的一个比较优秀的写法，之前我用了一个素数筛，结果烦死了，后来发现其实直接枚举这
	//个更加方便，而且它自己筛好了，x不断地除，那么对于每个质数，其倍数肯定已经不是x的因子了。
	//太妙了，因此我这里放了它的这种写法。
	if(x>1)	solve(x);//大素数
	printf("%lld\n",ans%MOD);
}

END

众所周知，$GCD$GCD是土拨鼠逃亡的意思。