Icebound and Sequence（非互质逆元 快速乘法）or（矩阵快速幂）

Icebound hates math. But Imp loves math. One day, Imp gave icebound a problem.  The problem is as follows. S=(∑ni=1qi） mod pS=(∑i=1nqi） mod p For given q,n,p, you need to help icebound to calculate the value of S.

输入描述:

The first line contains an integer T, denoting the number of test cases. The next T lines, each line contains three integers q,n,p, separated by spaces. 1≤T≤1001≤T≤100, 1≤n,q,p≤1091≤n,q,p≤109

输出描述:

For each test case, you need to output a single line with the integer S.

示例1

输入

复制

2 2 3 100 511 4 520

输出

复制

14 184

首先有一个基本的公式就是

a/b%c=a%（b*c）/b

此公式是用的就是在分母确定时 并且分子很大

那么我们列出等比数列求和公式

如果直接×会炸掉long long 那么我们就写一个快速加法进行乘法计算

#include<bits/stdc++.h> using namespace std; inline long long mult_mod(long long a,long long b, long long m) { long long res = 0; while(b){ if(b&1) res = (res+a)%m; a = (a+a)%m; b >>= 1; } return res; } int main() { int t; scanf("%d",&t); while(t--) { long long q,n,p; scanf("%lld%lld%lld",&q,&n,&p); long long mod=(q-1)*p; long long tmppow=1; long long tmpq=q; if(q==1) { long long ans=n%p; printf("%lld\n",ans); continue; } while(n) { if(n%2==1) tmppow=mult_mod(tmppow,tmpq,mod); n/=2; tmpq=mult_mod(tmpq,tmpq,mod); } tmppow--; if(tmppow<0) tmppow+=mod; long long ans=mult_mod(q,tmppow,mod)/(q-1); printf("%lld\n",ans); } }

对于能写出地推表达式的算式

我们都可以用矩阵快速幂在logn的时间内解决

#include<cstdio> #include<cstring> using namespace std; long long q,n,p; struct node { long long a[2][2]; } pos; node milt(node x,node y) { node res; memset(res.a,0,sizeof(res.a)); for(int i=0; i<2; i++) for(int j=0; j<2; j++) for(int k=0; k<2; k++) res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j])%p; return res; } long long pow(long long n) { node x,y; x.a[0][0]=1,x.a[0][1]=0,x.a[1][0]=0,x.a[1][1]=1; y.a[0][0]=1,y.a[0][1]=1,y.a[1][0]=0,y.a[1][1]=q; while(n!=0) { if(n%2==1) x=milt(x,y); y=milt(y,y); n/=2; } long long ans=(x.a[0][1]*q)%p; return ans; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%lld%lld%lld",&q,&n,&p); printf("%lld\n",pow(n)); } }