当前位置：首页 > news >正文

可做题2(矩阵快速幂，乘法逆元，exgcd)

news 来源：原创 2023/9/23 9:38:58

题目链接：可做题2 (nowcoder.com)

题目描述

若一个数列a满足条件an=an-1+an-2,n ≥ 3,而a1,a2为任意实数，则我们称这个数列为广义斐波那契数列。
现在请你求出满足条件a1=i，a2为区间[l,r]中的整数，且ak mod p=m的广义斐波那契数列有多少个。

输入描述:

本题包含多组数据，输入第一行包含一个正整数T，表示数据组数。对于每组数据：
一行六个用空格隔开的整数i,l,r,k,p,m，意义如题目描述所示。

输出描述:

输出共T行，每行一个数表示该组数据的答案。

示例1

输入

复制6 2 17 68 3 23 1 1 17 68 3 57 1 5 17 68 10 11 9 5 17 68 10 71 9 10 17 68 11 12 3 10 17 68 8 6 4

6
2 17 68 3 23 1
1 17 68 3 57 1
5 17 68 10 11 9
5 17 68 10 71 9
10 17 68 11 12 3
10 17 68 8 6 4

输出

复制3 1 4 1 5 9

备注:

对于所有数据，0 ≤ l ≤ r,1 ≤ p ≤ 109,0 ≤ m < p,T=10,0 ≤ i ≤ 1018,k ≥ 3。

思路：对于这个题一看斐波那契，数据又很大，应该立马就想到了矩阵快速幂，再接着看akmodp=m，可能又跟扩展欧几里得有关系，由于p可能不是质数，所以需要判断不互质的情况，然后使用扩展欧几里得或欧拉定理求解同余方程。

首先可以发现 ak=f(k-2)+f(k-1)*x;首先利用矩阵快速幂求出ak。可以利用矩阵a[2][2]={1,1,1,0}这样的一个矩阵，然后k次方就行了，也就是a[2][2]*(a[2][2]^(k-1)),然后算出ak，我们得到f[1][1]和f[2][1],即f(k-1)和f(k-2),然后exgcd解方程 , 每隔p/gcd 个就有一个解

如果l-x>1的话，结果就是：

(r-x)/(p/gcd)+1-(l-x-1)/(p/gcd)+1；

更详细题解：可做题2（Code+12月网络赛）（扩欧+矩阵快速幂）_Coco_T_的博客-CSDN博客

#include<bits/stdc++.h>
#define lmw ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int long long
//int n,m;
const int N=105;
int f[N][N],a[N][N];
// const int mod=1e9+7;
int c[N][N];
int i,l,r,k,pp,m,x,y;
int exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	int gcd=exgcd(b,a%b,x,y);
	int z=x;
	x=y;
	y=z-(a/b)*y;
	return gcd;
}
void mul(int c[],int a[],int b[][N]){
	int s[N]={0};
	for(int i=0;i<=2;i++){
		for(int j=0;j<=2;j++){
			s[i]=(s[i]+a[j]*b[j][i])%pp;
		}
	}
	memcpy(c,s,sizeof(s));
}
void mul(int c[N][N],int a[N][N]){
	int p[N][N]={0};    
	for(int i=1;i<=2;i++){
		for(int j=1;j<=2;j++){
			for(int k=1;k<=2;k++){
			p[i][j]=(p[i][j]+c[i][k]*a[k][j])%pp;				
			}
		}
	}
	memcpy(a,p,sizeof(p));
}
int cal(int x,int y){
	if(x<y) return 0;
	return (x-y)/pp+1;
}
int solve(int xx,int yy){
	int c=__gcd(xx,pp);
	if(yy%c!=0) return 0;
	xx/=c;
	yy/=c;
	pp/=c;
//	int xx,yy;
	int res=exgcd(xx,pp,x,y);
    x=(x*yy+pp)%pp;
	x=(pp+x%pp)%pp;
	return (int)(cal(r,x)-cal(l-1,x)); 
}
signed main(){
    lmw;
	int t;
	cin>>t;
	while(t--){
        a[1][1]=1,a[1][2]=1;
	    a[2][1]=1,a[2][2]=0;
		cin>>i>>l>>r>>k>>pp>>m;
		i%=pp;
		k-=3;
		f[1][1]=1,f[1][2]=1;
        f[2][1]=1,f[2][2]=0;
		while(k){
			if(k&1) mul(a,f);
			mul(a,a);
			k/=2;
		}
		int ans=f[1][1]%pp;
		int sum=((m-f[2][1]%pp*i%pp)%pp+pp)%pp;
//         cout<<ans<<" "<<sum<<" ";
		cout<<solve(ans,sum)<<"\n";
	}
}

AC代码：