[2020牛客暑期多校训练营第九场] E.Groundhog Chasing Death 唯一分解+欧拉降幂_综合

题目链接：E.Groundhog Chasing Death

题意

题意很简单，求 ${ \prod_{i=a}^b \prod_{i=c}^d gcd(x^i,y^j)}$ ，答案对998244353取模。
${(0≤a,b,c,d≤3*10^6，0<x,y≤10^9，a≤b，c≤d)}$

题解

暴力 ${O(n^2logn)}$ 的时间复杂度，很明显不合情理，我们需要分析题目转化求解。
我们可以从唯一分解定理入手。
(唯一分解定理：任何一个大于1的自然数N，如果N不为质数，都可以分解为有限个质数的乘积 ${N=P_1^{a_1}P_2^{a_2}P_3^{a_3}......P_n^{a_n}}$ ，这里 ${p_1<p_2<...<p_n}$ 均为质数，其中指数 ${a_i}$ 为正整数。）

很容易想到gcd(a,b)为a,b唯一分解后，出现公共质数最小指数次方的乘积。
那么此题可以转化为：

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

${p_1^{\sum_{i=a}^{i=b}\sum_{j=c}^{j=d} min(a_1*i,b_1*j)}*p_2^{\sum_{i=a}^{i=b}\sum_{j=c}^{j=d} min(a_2*i,b_2*j)}*.........*p_x^{\sum_{i=a}^{i=b}\sum_{j=c}^{j=d} min(a_x*i,b_x*j)}}$

（x为a,b唯一分解后出现公共质数的个数， ${a_i,b_i}$ 分别对应a,b唯一分解后该质数所对应的指数）

现在只要处理了 ${\sum_{i=a}^{i=b}\sum_{j=c}^{j=d} min(a_1*i,b_1*j)}$ 这类式子，本题基本就迎刃而解了。

我们可以枚举i，取 ${t=a_1*i/b_1}$
如果 ${j≥t，可知a1*i≤b1*j}$ ，此时答案为 ${a_1*i*(d-t+1)}$
如果 ${j<t，此时答案为b_1*(c+c+1+.....+t-1)}$
注意 t 和区间 [c,d]的位置关系。

注意在计算 ${\sum_{i=a}^{i=b}\sum_{j=c}^{j=d} min(a_1*i,b_1*j)}$ 的过程中可能需要取模，由于我们求的是指数，所以根据欧拉降幂指数取模应取 ${\phi(mod)}$

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
//extern "C"{void *__dso_handle=0;}
typedef long long ll;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define lowbit(x) x&-xconst double PI=acos(-1.0);
const double eps=1e-6;
const ll mod=998244353;
const int inf=0x3f3f3f3f;
const int maxn=1e5+10;
const int maxm=100+10;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll gcd(ll a,ll b)
{return b==0?a:gcd(b,a%b);
}
ll qpow(ll a,ll b)
{ll ans=1;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans%mod;
}
ll fac[2][105][2],fatcnt=0;
ll getfactors(ll x,int num)
{fatcnt=0;ll tmp=x;for(int i=2;i<=sqrt(x);i++){fac[num][fatcnt][1]=0;if(tmp%i==0){fac[num][fatcnt][0]=i;while(tmp%i==0){tmp/=i;fac[num][fatcnt][1]++;}fatcnt++;}}if(tmp>1){fac[num][fatcnt][0]=tmp;fac[num][fatcnt][1]=1;fatcnt++;}return fatcnt;
}
struct Node
{ll p,numx,numy,val;Node(ll p,ll numx,ll numy,ll val){this->p=p;this->numx = numx;this->numy = numy;this->val = val;}
};
vector<Node> m;
ll phi(ll p)
{return p-1;
}
int main()
{ll a,b,c,d,x,y;scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&d,&x,&y);ll ans=1;ll g = gcd(x,y);if(g==1){printf("1\n");return 0;}ll lenx = getfactors(x, 0);ll leny = getfactors(y, 1);for(int i=0;i<lenx;i++)for(int j=0;j<leny;j++)if(fac[0][i][0]==fac[1][j][0])m.pb(Node(fac[0][i][0],fac[0][i][1],fac[1][j][1],0));for(int k=0;k<m.size();k++)for(ll i=a;i<=b;i++){ll t=ceil(m[k].numx*1.0*i/m[k].numy);if(t<=d){ll len=d-t+1;if(t<c) len=d-c+1;m[k].val=(m[k].val+(m[k].numx*i%phi(mod))*len)%phi(mod);}if((t-1)>=c){ll r=min(d, t-1);m[k].val=(m[k].val+(m[k].numy*(c+r)%phi(mod))*(r-c+1)/2)%phi(mod);}}for(int k=0;k<m.size();k++) ans=ans*qpow(m[k].p, m[k].val)%mod;printf("%lld\n",ans);
}