[牛客月赛][初级][49]-D题 梵 快速幂求逆元题解

3
2 4
2 4
2 4

1
1
1

总结一下题意其实就是函数    

而  的图像大致如图所示

 那么的最大值其实就是两个零点的相减，也就是

 现在我们得出结论以后再回来看怎么求出来

 我们先来看单个是什么 我们把打开就是如下这个式子

再化简一下就是

那么知道了以后我们来看怎么求

我们将上式划分为3部分逐一分析

第一部分：  

这一部分我们可以通过等差数列求和公式总结出来 就是   

第二部分：

这一部分我们可以通过等差数列求和公式总结出来 就是  

第三部分：

这一部分其实就是n个1加起来 那么其实就是n

那么再将这些总结带回原式即可求出

还有就是快速幂求逆元，在mod一个数的情况下除以一个数等于乘以一个数的逆元

在c++中除并不好处理所以我们用乘以一个数的逆元，在本题中就是乘以2和6的逆元

为了避免我们在MOD过程中

MOD出来了负数

那么我们先MOD再加MOD再MOD就一定是一个正数

这是MOD的一个小技巧

#include
using namespace std;
typedef long long LL;
const LL MOD=998244353;
//快速幂
LL qmi(LL a,LL b,LL p){
    LL ans=1;
    while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}
LL a,b;
//逆元
LL inv(LL x){
   return (qmi(x,MOD-2,MOD)%MOD+MOD)%MOD;
}
LL sum(LL x){
    LL ans1=x*(x+1)%MOD*(2*x+1)%MOD*inv((LL)6)%MOD;//第一部分
    LL ans2=(a+b)%MOD*x%MOD*(x+1)%MOD*inv((LL)2)%MOD;//第二部分
    LL ans3=a*b%MOD*x%MOD;//第三部分
    LL ans=((-ans1+ans2-ans3)%MOD+MOD)%MOD;
    return ans;
}
void solve(){
     cin>>a>>b;
     LL ans=(( sum(b)-sum(a) )%MOD+MOD)%MOD;
     cout<>T;
    while(T--){
        solve();
    }
    return 0;
}