2020牛客暑期多校训练营（第九场）E-Groundhog Chasing Death

题目大意

给出，求出

解题思路

• 看到这样的数据范围和数的大小，显然是不可能用类似两重循环的暴力方法搞过的。
  所以，我们要开始尝试用分解的方式来解决。看到求gcd，就应该尝试对给出的数分解质因数，然后对每个质因数分别讨论其幂次。那么，这个问题就转化为了个子问题。
• 这样，每个子问题都形如给出，要求出
• 那么可以枚举这个最小值，是在取到还是在取到，再求出每种情况的方案数。
  这里要注意的是：处理好的情况，注意如果要对幂次取模，按照欧拉/费马小定理，模数应该取 。

综上，这种算法运算的次数就是可行的，大约次。

AC代码

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
int u,v,ans;
int qpow(int x,int y)
{
    if(!y) return 1;
    int z=qpow(x,y>>1);
    z=1ll*z*z%mod;
    if(y&1) z=1ll*z*x%mod;
    return z;
}
int get(int x,int y)
{
    int z=0,i,j;
    for(i=1;i<=x;i++)
    {
        j=u*i/v;
        if(j>y) j=y;
        z=(z+(j+1LL)*j/2%(mod-1)*v)%(mod-1);
        z=(z+1LL*i*(y-j)%(mod-1)*u)%(mod-1);
    }
    return z;
}
int main()
{
    int a,b,c,d,x,y,z,m,i;
    scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&x,&y);
    ans=1,m=max(x,y);
    for(i=2;i*i<=max(x,y);i++)
    {
        u=v=0;
        while(x%i==0) u++,x/=i;
        while(y%i==0) v++,y/=i;
        if (!u || !v) continue;
        z=(2ll*(mod-1)+get(b,d)+get(a-1,c-1)-get(a-1,d)-get(b,c-1))%(mod-1);
        ans=1ll*ans*qpow(i,z)%mod;
    }
    if(x>1 && x==y)
    {
        u=v=1;
        z=(2ll*(mod-1)+get(b,d)+get(a-1,c-1)-get(a-1,d)-get(b,c-1))%(mod-1);
        ans=1ll*ans*qpow(x,z)%mod;
    }
    printf("%d",ans);
}