Groundhog Chasing (数论&质因数）

Groundhog Chasing (数论&质因数）

思路：枚举质因子贡献。

然后第一维暴力，第二维用公式求和。

第二维分三种情况：

设当前因子为 $s$， $x$的该因子个数为 $c_1$, $y$的该因子个数为 $c_2$。

1.当 $i\times c_1\le c\times c_2$ 时。

显然都为：从 $[c,d]$贡献都为 $c_1i$

2.当 $i\times c_1\ge d\times c_2$时。

显然从 $j\in[c,d]$贡献为： $c_2j$，即： $\dfrac{c_2(d-c+1)(c+d)}{2}$

3.当 $c_1i\in(cc_2,dc_2)$时 令 $mid=\dfrac{c_1i}{c_2}$

从 $[c,mid]$贡献为： $\dfrac{c_2(mid-c+1)(c+mid)}{2}$

从 $[mid+1,r]$贡献为： $c_1i\times(r-mid)$

时间复杂度： $O((b-a)log(sum))$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=998244353;
#define mst(a,b) memset(a,b,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
ll f(int l,int r){ return 1LL*(l+r)*(r-l+1)>>1;}
ll ksm(ll a,ll n){ll ans=1;while(n){if(n&1) ans=ans*a%mod;a=a*a%mod;n>>=1;}return ans;
}
int a,b,c,d,x,y;
vector<int>dir;
int main(){scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&x,&y);int g=__gcd(x,y);for(int i=2;i*i<=g;i++){if(g%i==0){dir.pb(i);while(g%i==0) g/=i;}} if(g>1) dir.pb(g);ll ans=1;for(int s:dir){int x1=x,y1=y,c1=0,c2=0;while(x1%s==0) x1/=s,c1++;while(y1%s==0) y1/=s,c2++;ll sum=0;for(int i=a;i<=b;i++){if(i*c1<=c*c2) sum+=1LL*(d-c+1)*i*c1;else if(i*c1>=d*c2) sum+=f(c,d)*c2;else sum+=f(c,i*c1/c2)*c2+1LL*(d-i*c1/c2)*i*c1;sum%=(mod-1);}ans=ans*ksm(s,sum)%mod;//printf("%lld\n",ans);}printf("%lld\n",ans);return 0;
}