跳到主要内容

快速幂

AcWing 875. 快速幂​

题目​

https://www.acwing.com/problem/content/877/ 给定 n 组ai,bi,pia_i,b_i,p_i，对于每组数据，求出 aibimodpia_i^{b_{i}}modp_i 的值。

思路​

a”=a×a×…×aa”=a×a×…×a,暴力的计算需要O(n)的时间 快速幂使用二进制拆分和倍增思想，仅需要O(Iog)的时间。 对n做二进制拆分，例如，313=3(1101)2=38⋅34⋅313^{13}=3^{(1101)_2}=3^8·3^4·3^1 对Q做平方倍增，例如，31,32,34,38…3^1,3^2,3^4,3^8… n有logn+1个二进制位，我知道了al,a2,a4,a8,,a2logna^l,a^2,a^4,a^8,,a^{2logn}后 只需要计算logn+1次乘法就可以了。

代码​

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
LL n,a,b,p;

int qmi(LL a,int b,int p){
    int res=1;
    while (b){
        if (b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}


int main() {
    cin>>n;
    while (n--)
    {
        cin>>a>>b>>p;
        cout<<qmi(a,b,p)<<endl;
    }
    return 0;
}

高精度快速幂​

题目​

P1045 [NOIP2003 普及组] 麦森数 https://www.luogu.com.cn/problem/P1045 任务：输入 P(1000<P<3100000)P(1000<P<3100000)，计算 2P−12^{P}-1 的位数和最后 500500 位数字（用十进制高精度数表示）

思路​

高精度+快速幂 2P−12^P-1的位数为(int)p∗log102+1(int) p*log_{10}2+1

快速幂：

1.对指数p做拆分，对底数a做倍增。 2.计算res,a均调用高精度乘法。

高精度：

1.借助一个临时数组t保存并返回结果。 2.a,b数组的位数均取500位就足够了。

代码​

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int p;
const int N=500;
vector<int> a(N),res(N);

vector<int> mul(vector<int> &a,vector<int> &b){
    vector<int> t(N*2);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        {
            t[i+j]+=a[i]*b[j];
            t[i+j+1]+=t[i+j]/10;
            t[i+j]%=10;
        }
    return t;
}

void qmi(int p){
    res[0]=1,a[0]=2;
    while (p){
        if (p&1) res= mul(res,a);
        a= mul(a,a);
        p>>=1;
    }
    res[0]--;
}

int main() {
    cin>>p;
    cout<<int(p*log10(2))+1<<endl;
    qmi(p);
    for(int i=0,k=499;i<10;i++) {
        for (int j = 0; j < 50; j++, k--)
            cout << res[k];
        cout<<endl;
    }

    return 0;
}

矩阵快速幂​

题目​

思路​

矩阵乘法： 设A为m×p的矩阵，B为p×n的矩阵则称m×n的矩阵C为矩阵A与B的乘积。 则C的第ⅰ行第j列元素为: Cij=∑k=1pa‾ikb‾kj=ai1 b1j+ai2 b2j+⋯+aipbpj\mathrm{C}_{\mathrm{ij}}=\sum_{\mathrm{k}=1}^{\mathrm{p}} \underline{a}_{\mathrm{ik}} \underline{b}_{\mathrm{kj}}=\mathrm{a}_{\mathrm{i} 1} \mathrm{~b}_{1 \mathrm{j}}+\mathrm{a}_{\mathrm{i} 2} \mathrm{~b}_{2 \mathrm{j}}+\cdots+\mathrm{a}_{\mathrm{ip}} \mathrm{b}_{\mathrm{pj}}

image.png

代码​

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int mod=1e9+7;

struct matrix{
    LL c[101][101];
    matrix(){ memset(c,0,sizeof c);}
}A,res;
LL n,k;

matrix operator * (matrix &x,matrix &y){
    matrix t;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                t.c[i][j]=(t.c[i][j]+x.c[i][k]*y.c[k][j])%mod;
    return t;
}

void qmi(LL k)
{
    for(int i=1;i<=n;i++) res.c[i][i]=1;//单位矩阵
    while (k){
        if (k&1) res=res*A;
        A=A*A;
        k>>=1;
    }
}

int main() {
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>A.c[i][j];
    qmi(k);
    for(int i=1;i<=n;i++) {
        for (int j = 1; j <= n; j++)
            cout << res.c[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

0%