[bzoj 1409] Password 矩阵快速幂+欧拉函数

时间:2022-09-19 00:11:38

考试的时候想到了矩阵快速幂+快速幂,但是忘(bu)了(hui)欧拉定理。

然后gg了35分。

题目显而易见,让求一个数的幂,幂是斐波那契数列里的一项,考虑到斐波那契也很大,所以我们就需要欧拉定理了

p是素数,所以可以搞 [bzoj 1409] Password 矩阵快速幂+欧拉函数

然后我们用矩阵快速幂求出幂,然后快速幂即可解决问题

#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 矩阵快速幂+欧拉函数的更多相关文章

  1. HDU4549 M斐波那契数列 矩阵快速幂&plus;欧拉函数&plus;欧拉定理

    M斐波那契数列 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Total Sub ...

  2. HDU 3221 矩阵快速幂&plus;欧拉函数&plus;降幂公式降幂

    装载自:http://www.cnblogs.com/183zyz/archive/2012/05/11/2495401.html 题目让求一个函数调用了多少次.公式比较好推.f[n] = f[n-1 ...

  3. hdu 5895&lpar;矩阵快速幂&plus;欧拉函数&rpar;

    题目链接: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 ...

  4. HDU 4549 矩阵快速幂&plus;快速幂&plus;欧拉函数

    M斐波那契数列 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Total Sub ...

  5. Product Oriented Recurrence&lpar;Codeforces Round &num;566 &lpar;Div&period; 2&rpar;E&plus;矩阵快速幂&plus;欧拉降幂&rpar;

    传送门 题目 \[ \begin{aligned} &f_n=c^{2*n-6}f_{n-1}f_{n-2}f_{n-3}&\\ \end{aligned} \] 思路 我们通过迭代发 ...

  6. hdu4549 矩阵快速幂 &plus; 欧拉降幂

    R - M斐波那契数列 Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit  ...

  7. Super A&Hat;B mod C (快速幂&plus;欧拉函数&plus;欧拉定理)

    题目链接:http://acm.fzu.edu.cn/problem.php?pid=1759 题目:Problem Description Given A,B,C, You should quick ...

  8. hdu 2814 快速求欧拉函数

    /** 大意: 求[a,b] 之间 phi(a) + phi(a+1)...+ phi(b): 思路: 快速求欧拉函数 **/ #include <iostream> #include & ...

  9. BZOJ 1297 迷路&lpar;矩阵快速幂&rpar;

    很容易想到记忆化搜索的算法. 令dp[n][T]为到达n点时时间为T的路径条数.则dp[n][T]=sigma(dp[i][T-G[i][n]]); 但是空间复杂度为O(n*T),时间复杂度O(n*n ...

随机推荐

  1. How to use the Visual Studio

    推荐一个提供VS配色方案的一个网站:StudioStyles,域名和网站同名:http://studiostyl.es/ 2. 整行剪切:Ctrl + X.光标不要选中任何文字,然后按这个快捷键就可以 ...

  2. 排序算法 2 qsort 库函数,泛型函数

    _____谈谈排序算法 交换排序——>冒泡排序-->快速排序 选择排序——>简单选择排序——>堆排序 插入排序——>直接插入排序——>希尔排序 _____排序算法对 ...

  3. dedecms网站栏目增加缩略图的方法-测试通过

    有时候因为网站功能需求,我们需要为织梦程序的栏目页添加缩略图功能,这里有一个栏目添加缩略图的方法,供大家参考 涉及到文件如下(注意备份): dede/catalog_add.php dede/cata ...

  4. Kali Linux 2016&period;2初体验使用总结

    Kali Linux 2016.2初体验使用总结 Kali Linux官方于8月30日发布Kali Linux 2016的第二个版本Kali Linux 2016.2.该版本距离Kali Linux  ...

  5. hdu-----2491Priest John&&num;39&semi;s Busiest Day(2008 北京现场赛G&rpar;

    Priest John's Busiest Day Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav ...

  6. 存储过程往拼接的sql语句中传递日期值

    存储过程往拼接的sql语句中传递日期值 declare @start datetime declare @end datetime set @start='2014-3-1' set @end='20 ...

  7. CREATE DATABASE RoomReservation

    要从我的模型开始构建我的RoomReservation数据库对象,我将创建表对象. 要在SQL Server中创建表,我需要使用CREATE TABLE语句. 使用CREATE TABLE语句,我将能 ...

  8. python基础之Day20part1

    一.hash算法 什么是hash? 类似工厂加工的过程,传bytes串,经过运算返回字符 hash相当于工厂,传给hash算法的内容是原材料,hash值为产品 为何用hash? hash三大特性: 1 ...

  9. mysql的innodb存储引擎

    innodb是支持事务的存储引擎,支持ACID特性的ACID(指数据库事务正确执行的四个基本要素的缩写) 包含:原子性(Atomicity).一致性(Consistency).隔离性(Isolatio ...

  10. Maven的课堂笔记3

    8 仓库管理 仓库可以分为三种:1.本地仓库(本机).2.私服(公司局域网内的maven服务器).3.*仓库(互联上,例如 struts2官网,或者hibernate官网) 可以根据maven坐标定 ...