題目分析：因為涉及到了 gcd 的乘積運算，那么易知不同質因子的貢獻是相互獨立的，首先我們就可以先將 x 和 y 進行質因子分解，那么對于質因子 p 來說，設 cntx[ p ] 為 p 在 x 中出現的次數，cnty[ p ] 為 p 在 y 中出現的次數，不難看出，需要這兩個數同時大于 0 才有貢獻，如果其中一者為 0 的話，那么其表示的質因子就是 p^0 = 1 ，gcd 求出來顯然也就是 1 了，對答案沒有貢獻
到此，cntx[ p ] 和 cnty[ p ]?都大于 0 ，那么質因子 p 的 gcd 就是?，也就是?，這也就提醒我們可以對指數單獨處理，最后求一下 p 的冪次再乘起來就是答案了
此時我們可以對指數稍微打表找一下規律，打表程序如下（可以自己更改一下 i 和 j 的取值范圍，分別代表 [ a , b ] 和 [ c , d ] ）：
這樣就可以將 ( b - a + 1 ) * ( d - c + 1 ) 的時間復雜度優化為 ( b - a + 1 ) 或者 ( d - c + 1 ) 了，因為知道了是等差數列，我們可以求出三項：第一項，第二項，最后一項，根據第一項和第二項得出公差，根據第一項、最后一項和公差計算出等差數列的長度，這樣最后常數項的長度也能計算得出了
有個小坑就是，如果指數直接進行運算的話，會爆 long long ，可以用費馬小定理降冪，一方面是保證指數在數據范圍內，另一方面是加速快速冪的運算
因為我用了 map 參與質因子分解，所以總的時間復雜度為 ( b - a + 1 ) * logn * logn
代碼： ?
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;const int mod=998244353;const int mmod=mod-1;map<int,int>mpx,mpy;LL q_pow(LL a,LL b)
{LL ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;
}void only(map<int,int>&mp,int x)
{for(int i=2;i*i<=x;i++){while(x%i==0){mp[i]++;x/=i;}}if(x!=1)mp[x]++;
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);int a,b,c,d,x,y;scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&x,&y);a=max(a,1);c=max(c,1);only(mpx,x),only(mpy,y);LL ans=1;for(auto it:mpx){int num=it.first,cntx=it.second,cnty=mpy[num];if(cntx==0||cnty==0)continue;LL res=0;//指數 for(int i=a;i<=b;i++){LL mmin=min(1LL*i*cntx,1LL*c*cnty),mmax=min(1LL*i*cntx,1LL*d*cnty);//第一項和最后一項LL delta=min(1LL*i*cntx,1LL*(c+1)*cnty)-mmin;//公差LL k=d-c+1;//一共有k項LL n;//有幾項是等差數列if(delta==0)n=k;elsen=(mmax-mmin)/delta+1;LL sum=(n*mmin%mmod+(n*(n-1)/2)%mmod*delta%mmod)%mmod;//等差數列求和公式res=(res+sum%mmod+1LL*(k-n)*mmax%mmod)%mmod;}ans=ans*q_pow(num,res)%mod;}printf("%lld\n",ans);return 0;
}
