E-Groundhog Chasing Death

链接：https://ac.nowcoder.com/acm/contest/5674/E
来源：牛客网

题意：

给你a,b,c,d,x,y，让你求a<=i<=b,c<=j<=d,范围内gcd(x^i,y^j)的连乘的积，并取模998244353

solution：

先处理一下x,y的值，将x，y分解成若干个不同的素数因子相乘，并且记录每个素数因子的个数。由于我们要求的是gcd的连乘，所以根据最小公倍数的原理可知只有在x和y中都出现的素数因子才可能在gcd里出现，所以我们将x和y中不相同的素数因子（即只在x，y其中一个因子中出现）的素数因子删去
然后对于每个素数因子，我们进行一次i=[a,b]的循环，我们记p为素数因子，cntx，cnty分别代表p在x，y中出现的次数,sum是连乘过程中p的总个数,now=cntx*i,我们可以知道在cnty * j<=now (j=[c,d])的时候可以知道gcd(p^now,p^(cnty * j))=p^(cnty * j)，而当cnty * j>now时，gcd(p^now,p^(cnty * j))=p^now，这样我们就可以推出一个式子O(1)求解第i次的p的个数

now/cnty <c  sum=sum+(d-c+1)*now
c<=now/cnty<d sum=sum+(now/cnty-c+1)*(cnty+c)/2*cnty+(d-now/cnty)*now
d<=now/cnty sum=sum+(d-c+1)*(d+c)/2*cnty

代码

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int mod =998244353;
typedef pair<int,int> P;
ll a,b,c,d,x,y;
int cntx[100000],cnty[100000],p[100000];
ll fpow(ll a,__int128 x)
{
    ll ans=1;
    while(x)
    {
        if(x&1)ans=ans*a%mod;
        a=a*a%mod;
        x/=2;
    }
    return ans;
}
int main()
{
    cin>>a>>b>>c>>d>>x>>y;
    int num=0;
    for(int i=2;i*i<=min(x,y);i++)
    {
        int cnt=0,cnt1=0;
        while(x%i==0)
        {
            cnt++;x/=i;
        }
        while(y%i==0)
        {
            cnt1++;y/=i;
        }
        if(cnt&&cnt1)
        {
            cntx[num]=cnt;
            cnty[num]=cnt1;
            p[num++]=i;
        }
    }
    if(min(x,y)!=1)
    {
        if(x>y)
        {
            int cnt=0;
            while(x%y==0)
            {
                cnt++;
                x/=y;
            }
            cntx[num]=cnt;
            cnty[num]=1;
            p[num++]=y;
        }
        else
        {
            int cnt=0;
            while(y%x==0)
            {
                cnt++;
                y/=x;
            }
            cntx[num]=1;
            cnty[num]=cnt;
            p[num++]=x;
        }
    }
    ll res=1;
    for(int i=0;i<num;i++)
    {
        ll now=(a-1)*cntx[i];
        __int128 sum=0;
        for(int j=a;j<=b;j++)
        {
            now+=cntx[i];
            ll qaq=now/cnty[i];
            if(qaq<c)
                sum=sum+(d-c+1)*now;
            else if(qaq>=c)
            {
                if(qaq<d)
                    sum=sum+(qaq-c+1)*(qaq+c)/2*cnty[i]+(d-qaq)*now;
                else
                    sum=sum+(d-c+1)*(d+c)/2*cnty[i];
            }
        }
        res=res*fpow(p[i],sum)%mod;
    }
    printf("%lld",res);
    return 0;
}