欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

分治之快速幂及其取余 from yty (luogu p1226)

程序员文章站 2022-05-14 17:17:27
...

    最近讲了分治的几大点知识,第一块讲的就是快速幂,还顺便扩了一下取余里的同余原理(a*b%k=(a%k)(b%k)%k)借着洛谷里p1226的一道题,详细记录一下这个知识点。

    快速幂的精髓,就是把一个幂运算中的指数化成几个2的幂的和(也就是化成二进制),然后整个的值就可以化成几个指数是二的幂的数的乘积。比个例子,就是 a^19= a^16*a^2*a^1。16、2、1都是2的幂,原本要算19次,现在只需要6次,大大减少了时间。

    

总结刚才的思路,则有分治之快速幂及其取余 from yty (luogu p1226)

    接下来话不多说,上题。

题目描述

输入b,p,k的值,求b^p mod k的值。其中b,p,k*k为长整型数。

输入输出格式

输入格式:

三个整数b,p,k.

输出格式:

输出“b^p mod k=s”

s为运算结果

输入输出样例

输入样例#1:
2 10 9
输出样例#1:
2^10 mod 9=7




这道题就完完全全一道模版题,简单的,那么上代码解说

#include<bits/stdc++.h>
using namespace std;
int main()
{
 long long b,p;
 int k;
cin>>b>>p>>k;//读入b p k,好像scanf用不来。他们表示b^p%k。 
 int x=b,y=p,ans=1;//ans是最终输出的结果 
 x%=k;//一开始就要对他取一次余  至于为什么,看同余公式你就懂 
 while(y!=0)//开始主体 
 {
     if(y%2==1)//指数除以二,就是对它进行二进制转化 
    {               //如果结果是1,就表示这个二进制位是1 
        ans=ans*x%k;//如果是1,就要在原来基础上乘上b的2的幂次 
    }
    y/=2;
    x=x*x%k;//每次循环结束都要平方一下,原因只能意会不能言传 
 }
 cout<<b<<'^'<<p;
 cout<<' ';
 cout<<"mod";
 cout<<' '<<k<<'=';
 cout<<ans;


 return 0;
}
就是这样,快速幂也没其他可以说的了