考试的时候想到了矩阵快速幂+快速幂,但是忘(bu)了(hui)欧拉定理。
然后gg了35分。
题目显而易见,让求一个数的幂,幂是斐波那契数列里的一项,考虑到斐波那契也很大,所以我们就需要欧拉定理了
p是素数,所以可以搞
然后我们用矩阵快速幂求出幂,然后快速幂即可解决问题
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; #define pos(i,a,b) for(int i=(a);i<=(b);i++) #define Ma 50000 #define LL long long LL prime[Ma],num_prime; LL isnotprime[Ma]={1,1}; LL c,ou; LL m,p,n,q; struct matrix{ LL a[10][10]; matrix(){ memset(a,0,sizeof(a)); } }; matrix mul(matrix aa,matrix b){ matrix c; pos(i,0,1){ pos(j,0,1){ c.a[i][j]=0; pos(k,0,1){ c.a[i][j]=(c.a[i][j]+aa.a[i][k]*b.a[k][j])%ou; } } } return c; } void getprime(){ pos(i,2,Ma-1){ if(!isnotprime[i]){ prime[num_prime++]=i; } for(int j=0;j<num_prime&&i*prime[j]<Ma;j++){ isnotprime[i*prime[j]]=1; if(!(i%prime[j])){ c++; break; } } } } matrix init(){ matrix res; pos(i,0,1){ pos(j,0,1) res.a[i][j]=(i==j); } return res; } matrix ks(matrix aa,int k){ matrix res=init(); while(k){ if(k&1) res=mul(res,aa); k>>=1; aa=mul(aa,aa); } return res; } LL oula(LL nn){ LL mm=(int)sqrt(nn+0.5); LL an=nn; for(int i=0;prime[i]<=mm;i++){ if(nn%prime[i]==0){ an=an/prime[i]*(prime[i]-1); while(nn%prime[i]==0) nn/=prime[i]; } } if(nn>1) an=an/nn*(nn-1); return an; } LL qpow(LL a,LL k,LL c){ LL an=1; a=a%c; while(k){ if(k&1){ an=(an*a)%c; } k>>=1; a=(a*a)%c; } return an; } LL ans; int main(){ getprime(); scanf("%lld%lld",&m,&p); while(m--){ ans=0; scanf("%lld%lld",&n,&q); ou=oula(q); matrix A; A.a[0][0]=1; A.a[0][1]=1; A.a[1][0]=1; A.a[1][1]=0; matrix res=ks(A,n-1); LL tmp=res.a[0][0]; //cout<<"ou="<<ou<<" tmp="<<tmp<<endl; ans=qpow(p,tmp,q)%q; printf("%lld\n",ans); } return 0; }
[bzoj 1409] Password 矩阵快速幂+欧拉函数的更多相关文章
-
HDU4549 M斐波那契数列 矩阵快速幂+欧拉函数+欧拉定理
M斐波那契数列 Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Sub ...
-
HDU 3221 矩阵快速幂+欧拉函数+降幂公式降幂
装载自:http://www.cnblogs.com/183zyz/archive/2012/05/11/2495401.html 题目让求一个函数调用了多少次.公式比较好推.f[n] = f[n-1 ...
-
hdu 5895(矩阵快速幂+欧拉函数)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5895 f(n)=f(n-2)+2*f(n-1) f(n)*f(n-1)=f(n-2)*f(n-1)+2 ...
-
HDU 4549 矩阵快速幂+快速幂+欧拉函数
M斐波那契数列 Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Sub ...
-
Product Oriented Recurrence(Codeforces Round #566 (Div. 2)E+矩阵快速幂+欧拉降幂)
传送门 题目 \[ \begin{aligned} &f_n=c^{2*n-6}f_{n-1}f_{n-2}f_{n-3}&\\ \end{aligned} \] 思路 我们通过迭代发 ...
-
hdu4549 矩阵快速幂 + 欧拉降幂
R - M斐波那契数列 Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submit ...
-
Super A^B mod C (快速幂+欧拉函数+欧拉定理)
题目链接:http://acm.fzu.edu.cn/problem.php?pid=1759 题目:Problem Description Given A,B,C, You should quick ...
-
hdu 2814 快速求欧拉函数
/** 大意: 求[a,b] 之间 phi(a) + phi(a+1)...+ phi(b): 思路: 快速求欧拉函数 **/ #include <iostream> #include & ...
-
BZOJ 1297 迷路(矩阵快速幂)
很容易想到记忆化搜索的算法. 令dp[n][T]为到达n点时时间为T的路径条数.则dp[n][T]=sigma(dp[i][T-G[i][n]]); 但是空间复杂度为O(n*T),时间复杂度O(n*n ...
随机推荐
-
How to use the Visual Studio
推荐一个提供VS配色方案的一个网站:StudioStyles,域名和网站同名:http://studiostyl.es/ 2. 整行剪切:Ctrl + X.光标不要选中任何文字,然后按这个快捷键就可以 ...
-
排序算法 2 qsort 库函数,泛型函数
_____谈谈排序算法 交换排序——>冒泡排序-->快速排序 选择排序——>简单选择排序——>堆排序 插入排序——>直接插入排序——>希尔排序 _____排序算法对 ...
-
dedecms网站栏目增加缩略图的方法-测试通过
有时候因为网站功能需求,我们需要为织梦程序的栏目页添加缩略图功能,这里有一个栏目添加缩略图的方法,供大家参考 涉及到文件如下(注意备份): dede/catalog_add.php dede/cata ...
-
Kali Linux 2016.2初体验使用总结
Kali Linux 2016.2初体验使用总结 Kali Linux官方于8月30日发布Kali Linux 2016的第二个版本Kali Linux 2016.2.该版本距离Kali Linux ...
-
hdu-----2491Priest John&#39;s Busiest Day(2008 北京现场赛G)
Priest John's Busiest Day Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Jav ...
-
存储过程往拼接的sql语句中传递日期值
存储过程往拼接的sql语句中传递日期值 declare @start datetime declare @end datetime set @start='2014-3-1' set @end='20 ...
-
CREATE DATABASE RoomReservation
要从我的模型开始构建我的RoomReservation数据库对象,我将创建表对象. 要在SQL Server中创建表,我需要使用CREATE TABLE语句. 使用CREATE TABLE语句,我将能 ...
-
python基础之Day20part1
一.hash算法 什么是hash? 类似工厂加工的过程,传bytes串,经过运算返回字符 hash相当于工厂,传给hash算法的内容是原材料,hash值为产品 为何用hash? hash三大特性: 1 ...
-
mysql的innodb存储引擎
innodb是支持事务的存储引擎,支持ACID特性的ACID(指数据库事务正确执行的四个基本要素的缩写) 包含:原子性(Atomicity).一致性(Consistency).隔离性(Isolatio ...
-
Maven的课堂笔记3
8 仓库管理 仓库可以分为三种:1.本地仓库(本机).2.私服(公司局域网内的maven服务器).3.*仓库(互联上,例如 struts2官网,或者hibernate官网) 可以根据maven坐标定 ...