正题
题目链接:https://www.luogu.com.cn/problem/P5137
题目大意
\(T\)组数据给出\(n,a,b,p\)求
\[\left(\sum_{0=1}^na^ib^{n-i}\right)\%p
\]
\(1\leq T\leq 10^5,1\leq n,a,b,p\leq 10^{18}\)
解题思路
这个数据很大，考虑倍增求。
设为答案\(f(n)\)，那么有
\[f(n)=f(\frac{n}{2})(a^{\frac{n}{2}}+b^{\frac{n}{2}})-a^{\frac{n}{2}}b^{\frac{n}{2}}
\]
\[f(n)=af(n-1)+b^{n}
\]
倍增维护就好了
时间复杂度\(O(T\log n)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#define ll long long
using namespace std;
ll n,a,b,p,T;
ll read(){
ll x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
ll fac(ll a,ll b){
ll c=(long double)a*b/p;
long double ans=a*b-c*p;
if(ans>=p)ans-=p;
else if(ans<0)ans+=p;
return ans;
}
signed main()
{
T=read();
while(T--){
n=read();a=read();b=read();p=read();
ll ans=1,k=0,B=1,A=1;
for(ll i=62;i>=0;i--){
ans=(fac(A,ans)+fac(B,ans))%p;
ans=(ans+p-fac(A,B))%p;
k*=2;B=fac(B,B);A=fac(A,A);
if((n>>i)&1){
k++;B=fac(B,b);A=fac(A,a);
ans=(fac(ans,a)+B)%p;
}
}
printf("%lld\n",ans);
}
return 0;
}