题目描述
给定a,b,c,d,x,y的值,求 。
输入描述
输入6个整数a,b,c,d,x,y。
输出描述
输出一个整数作为答案。
数据范围
样例
样例1
输入
1 2 1 2 8 4输出
2048样例2
输入
1 2 3 4 120 180输出
235140177
题解思路
看到本题数据范围,又看到连乘,盲猜可能要高精,但看到modulo,就可以想到边算边模可以避免使用高精。
当然如果直接暴力还是会炸,所以要试着进行分解。
但对于每个子问题,在幂次上,都形如:给出 ,求 。
先来一长串东西,现在又来一长串东西,不免会有点脑阔疼,其实不然。
我们不妨先固定其中一个值,再求另一个值,然后枚举我们所固定的值,这样一来,思路应该会清楚一点。
根据费马小定理 易得,在对幂数取模时,模数应为998244352。
当然如果是奆佬完全可以选择比这更有逼格easy的做法。
(打比赛时脑子已经坏掉了,欢迎奆佬们提出意见)
参考代码
#include <bits/stdc++.h> using namespace std; const int MAXN=1e5+10; const int MOD=998244353; const int mod=998244352; long long ksm(long long a,long long b) { long long ret=1; while(b) { if(b&1)ret=ret*a%MOD; a=a*a%MOD,b>>=1; } return ret; } long long a,b,c,d,x,y,ans=1; void solve(int v) { long long a1=0,b1=0; while(x%v==0) a1++,x/=v; while(y%v==0) b1++,y/=v; if(a1==0||b1==0)return ; long long tp=0; for(long long i=a;i<=b;i++) { long long j=a1*i/b1,tmp,now; if(j<c)tmp=(d-c+1)*i%mod*a1%mod; else if(j>=d)tmp=(c+d)*(d-c+1)/2%mod*b1%mod; else { now=(c+j)*(j-c+1)/2%mod*b1%mod; tmp=(now+(d-j)*i%mod*a1%mod)%mod; } tp=(tp+tmp)%mod; } ans=1ll*ans*ksm(v,tp)%MOD; } int main() { scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&d,&x,&y); bool flag=false; for(int k=2;k<=x;k++) if(x%k==0)solve(k); if(x>1)solve(x); printf("%lld\n",ans%MOD); }