快速幂

一、整数快速幂

  题目描述

    给你三个整数 b,p,k 求 bp mod k;

  输入格式

    一行三个整数 b,p,k

  输出格式

    输出 bp mod k=s

  就是模板,打出来很简单,但有一个地方容易出错。

  看如下两个代码:

#include <cstdio>
#include <iostream>
using namespace std;
long long Mod=1000;
long long Pow(long long a,long long b){
    long long ans=1;
    for(;b;b>>=1){
        if(b&1)ans*=a%Mod;
        a=(a*a)%Mod;
    }
    return ans;
}
int main(){
    long long n,m;
    scanf("%lld %lld %lld",&n,&m,&Mod);
    printf("%lld^%lld mod %lld=",n,m,Mod);
    printf("%lld\n",Pow(n,m)%Mod);
    return 0;
}

 

#include <cstdio>
#include <iostream>
using namespace std;
long long Mod=1000;
long long Pow(long long a,long long b){
    long long ans=1;
    for(;b;b>>=1){
        if(b&1)ans=ans*a%Mod;
        a=(a*a)%Mod;
    }
    return ans;
}
int main(){
    long long n,m;
    scanf("%lld %lld %lld",&n,&m,&Mod);
    printf("%lld^%lld mod %lld=",n,m,Mod);
    printf("%lld\n",Pow(n,m)%Mod);
    return 0;
}

显然第一个代码是错的,错在ans*=a%Mod这边,如果这么用的话,ans并没有取Mod,只对了a取Mod,这样会有什么后果呢?当ans过大的时候他就会溢出。(可能你们不会犯这样的错误但我就是智障的写成了第一个~~)

整数快速幂的原理大家都很清楚就不说了,应用的话。。。是个人应该都知道怎么用吧。

 

二、矩阵快速幂

  题目描述

    给定n×n的矩阵A,求Ak

  输入格式

    第一行两个整数n,k接下来n行每行n个数,表示Aij

  输出格式

    输出 矩阵Ak

    每个元素对109+7取mod

  说明/提示

     对于 100\%100% 的数据:1\le n \le 1001≤n≤100,0 \le k \le 10^{12}0≤k≤1012
, |A_{i,j}| \le 1000∣A
i,j∣≤1000

 

    

快速幂
/*
看了题面很简单,事实上他的确很简单

    如果你看明白了整数的快速幂,这个就很简单了,对k二进制分解,不断舍弃最低位直到k为0,如果它的最低位1就累加答案。

    记得×的时候单独开一个数组保存结果!!!!不然数组会不断累×。
*/
#include <cstdio>
#include<cstring>
#define ll long long
const int N=110,Mod=1e9+7;
ll a[N][N],ans[N][N],n,k;//数据mod1e9为什么还要longlong?
void Mul(){
    ll temp[N][N];
    memset(temp,0,sizeof(temp));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                temp[i][j]=(temp[i][j]+ans[i][k]*a[k][j]%Mod)%Mod;
    //如果没用long long乘法要强转long long不然比如1e9*1e9肯定会超int
    memcpy(ans,temp,sizeof(temp));
}
void Mulself(){
    ll temp[N][N];
    memset(temp,0,sizeof(temp));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                temp[i][j]=(temp[i][j]+a[i][k]*a[k][j]%Mod)%Mod;
    memcpy(a,temp,sizeof(temp));
}
int main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            scanf("%lld",&a[i][j]);
            ans[i][j]=a[i][j];
        }
    k--;//ans初始值为一次方,所以要求的k次方只需乘k-1次方
    for(;k;k>>=1){
        if(k&1)Mul();
        Mulself();
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            printf("%lld ",ans[i][j]);
        printf("\n");
    }
}
View Code

 

    

    

 

 
上一篇:NOI Online爆蛋记


下一篇:洛谷春季 ACM 多校训练第五周