2020牛客暑期多校训练营(第九场)E题 Groundhog Chasing Death_综合

题意

计算
$\prod_{i=a}^{b}\prod_{j=c}^{d}gcd(x^i,y^j)$

$0 \leq a,b,c,d \leq 3e6,0 < x,y \leq 1e9,a \leq b,c \leq d;$

题解

先求出x,y的GCD,在对GCD质因子分解,对于每一个计算出的质因子V;

计算出x中有cnt1个V,y中有cnt2个V;

之后枚举从a到b,对于枚举的一个i来说

x中有cnt1 ***** i个v,y中有cnt2*(c -> d)个V,则V对答案的贡献为
$V^{\sum_{j=c}^{d}min(cnt1*i,cnt2*j)}$

暴力枚举c到d肯定不行,考虑分类讨论

①cnt1 * V >= cnt2 * d

这种情况时,对于每一个j,cnt2 * j都是较小值,所以对于这种情况下:
$sum=\sum_{j=c}^{d}cnt2*j$
根据等差数列求和公式,很容易就计算出答案;

②cnt1 * V <= cnt2 * c

这种情况时,对于每一个j,cnt1 * i都是较小值,所以对于这种情况下:
$sum=\sum_{j=c}^{d}cnt1*i$
常数数列更加容易计算

③不是以上情况时

这种情况时,说明存在某个pos使得pos之前时都是cnt2 * j为较小值,pos及以后的j都是cnt1 * i为较小值;

这是直接二分pos存在分界位置,所以对于这种情况下:
$sum=\sum_{j=c}^{pos-1}cnt2*j+\sum_{j=pos}^{d}cnt1*i$
对于每一个质因子都计算出该贡献,连乘即为答案;

!!!注意sum在累加过程中会爆longlong,需要用__int128存,因此快速幂幂次项也要用__int128存

代码实现

/******************************* * Coder : He Shuo. * * Type : Original Work * *******************************/#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef __int128 LL;
const ll mo = 998244353;
ll fpow(ll a,LL b)///幂次项用__int128存
{ll s = 1;a %= mo;while(b){if(b & 1)s = s * a % mo;a = a * a % mo;b >>= 1;}return s;
}ll a,b,c,d,x,y;vector<ll>e;///存因子ll func(ll l,ll r,ll key,ll num)///二分寻找pos分界位置
{ll mid;while(l < r){mid = l + r >> 1;if(mid * num > key)r = mid;else l = mid + 1;}return l;
}int main()
{scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&d,&x,&y);ll gcd = __gcd(x,y);for(int i = 2;i * i <= gcd;++ i)///对gcd质因子分解{if(gcd % i == 0){e.push_back(i);while(gcd % i == 0)gcd /= i;}}if(gcd > 1)e.push_back(gcd);ll ans = 1;for(int pos = 0;pos < e.size();++ pos){ll v = e[pos];ll cnt1 = 0,cnt2 = 0;while(x % v == 0)x /= v,cnt1 ++;///对于每一个V计算出x有多少个;while(y % v == 0)y /= v,cnt2 ++;///对于每一个V计算出y有多少个;LL sum = 0;///!!sum会爆longlong,用__int128存;for(ll i = a;i <= b;i ++){LL res = 0;if(cnt1 * i >= cnt2 * d)res = (cnt2 * c + cnt2 * d) * (d - c + 1) / 2;///第一种情况,等差数列求和公式计算~else if(cnt1 * i <= cnt2 * c)res = (d - c + 1) * (cnt1 * i);///第二种情况,常数列求和简简单单~else///第三种情况,找到pos分界位置之后,简单计算一下~{ll pos = func(c,d,cnt1 * i,cnt2);res = (cnt2 * c + cnt2 * (pos - 1)) * (pos - c) / 2 + (d - pos + 1) * (cnt1 * i);}sum += res;}ans = (ans * fpow(v,sum)) % mo;///累乘计算答案~}printf("%lld",ans);
}///写完提交,Accepted你值得拥有~