hdoj5667 BestCoder Round #80 【费马小定理(膜拜)+矩阵快速幂+快速幂】
2024-08-24 03:24:41
#include<cstdio>
#include<string>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<math.h>
#include<queue>
#include<stdlib.h>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
/*
1 0 0
1 C 1
0 1 0
*/
/*费马小定理的运用【第一次,膜拜费马小定理】*/
LL n,a,b,c,p,q;
struct asd{
LL a[5][5];
};
asd mul(asd a1,asd a2)
{
asd ans;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
ans.a[i][j]=0;
for(int k=0;k<3;k++)
{
ans.a[i][j]+=a1.a[i][k]*a2.a[k][j];
ans.a[i][j]%=q;
}
ans.a[i][j]%=q;
}
}
return ans;
}
asd quickmul(LL g,asd z)
{
asd ans;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
if(i==j)
ans.a[i][j]=1;
else
ans.a[i][j]=0;
}
}
while(g)
{
if(g%2)
{
ans=mul(ans,z);
}
g/=2;
z=mul(z,z);
}
return ans;
}
LL liu(LL x,LL y)
{
LL ans;
ans=1;
while(y)
{
if(y%2)
ans=ans*x%p;
y/=2;
x=x*x%p;
}
return ans;
}
/***---先用矩阵快速幂算出次数,然后用快速幂算出答案-----***/
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&p);
if(n==1)
{
printf("1\n");
continue;
}
q=p-1;
if(a%p==0)
{
printf("0\n");
continue;
}
asd m;
m.a[0][0]=1;m.a[0][1]=0;m.a[0][2]=0;
m.a[1][0]=1;m.a[1][1]=c;m.a[1][2]=1;
m.a[2][0]=0;m.a[2][1]=1;m.a[2][2]=0;
asd ans;
ans=quickmul(n-2,m); //m矩阵的(n-1)次,之后还要×一个特定矩阵 z;PS:因为算出了的已经包括了两个,然后所以是n-2...搞了半个小时,然后被厂长发现...瞎几把连测试都不会...
// asd an;
// an.a[0][0]=1;an.a[0][1]=0;an.a[0][2]=0;
// an.a[1][0]=1;an.a[1][1]=2;an.a[1][2]=1;
// an.a[2][0]=0;an.a[2][1]=1;an.a[2][2]=0;
// an=quickmul(2,an);
// for(int i=0;i<3;i++)
// {
// for(int j=0;j<3;j++)
// printf("%d ",an.a[i][j]);
// printf("\n");
// }
// printf("%lld\n",liu(2,3));
// asd z;
// z.a[0][0]=b;
// z.a[1][0]=b;
// z.a[2][0]=0;
LL pp;
pp=(ans.a[1][0]*b+ans.a[1][1]*b)%q; //直接得出 次数
LL k;
k=liu(a,pp); //快速幂得出答案
printf("%lld\n",k%p);
}
return 0;
}
/*
可以这样测案例
100
1 3 3 3 233
2 3 3 3 233
3 3 3 3 233
4 3 3 3 233
5 3 3 3 233
*/
最新文章
- LeetCode---String
- JAVA使用POI操作excel
- 初次使用IDEA的相关技巧
- NOIP欢乐模拟赛 T1 解题报告
- Verilog之基本算数运算
- 9Types of Leader
- Laravel 部署安装到虚拟主机的方法(折腾了一周,终于成功部署,原来是虚拟机不加载.env,谢谢莫回首http://lxl520.com/index.php/archives/88/!)
- JVM——新生代与老年代
- AWstat(linux下)
- 1223. Chernobyl’ Eagle on a Roof(dp)&;&;poj3783
- Centos添加硬盘分区、挂载磁盘
- springmvc数组参数传递
- KEIL里 Volatile的用法
- ajax方式提交带文件上传的表单,上传后不跳转
- MapReduce运行流程分析
- mysql获取当前时间,前一天,后一天
- NIO/BIO
- vue表单控件绑定(表单数据的自动收集)
- Excel自动建组
- 门户级UGC系统的技术进化路线 [转]