题解 P1226 【【模板】快速幂||取余运算】

· · 题解

其实我也是看到了几位大佬的题解才明白的，现在分享一下题目的算法分析我的做法

首先是方法问题，这里我就引用一下大佬的解题过程，简直天衣无缝！！！！

从头开始。若当前 pp 为偶数，咱们不着急，只需把 xx 自乘，然后 p /= 2p/=2 （即考虑下一层，下几层会帮我们乘上 (x^2)^{p/2}(x 2 ) p/2 的）。

若当前 pp 为奇数，说明 x^p = x(x^2)^{(p-1)/2}x p =x∗(x 2 ) (p−1)/2 中前面那个 xx 的存在，ans = xans∗=x。然后继续考虑下一层（下几层会帮我们乘上 (x^2)^{(p-1)/2}(x 2 ) (p−1)/2 的）。注意，这里的 xx 不是指题目开始给出的 xx，而是当前层的 xx 应有的值，这跟上面的 basebase 是一样的。

也是稍稍模拟一下比较好理解。

·假设我们拿到了 x = 3x=3，并且 p = 11p=11。想求 3^{11}3 11 。

·第一层循环。b = 11b=11，一个奇数。将 3^{11}3 11 分解为 3^1 (3^2)^53 1 ∗(3 2 ) 5 来看。本层只需把 ans = 3^1ans∗=3 1 。那后面的呢？我们到下一层再搞定。下几层的总目标是让 ans = (3^2)^5ans∗=(3 2 ) 5 ，也就是让 ans = 9^5ans∗=9 5 。来到下一层的方法是 x = 3*3 = 9x=3∗3=9 且 b = 11 / 2 = 5b=11/2=5。

·第二层循环几乎独立于第一层存在。b = 5b=5，一个奇数。将 9^{5}9 5 分解为 9^1 (9^2)^29 1 ∗(9 2 ) 2 来看。本层只需把 ans = 9^1ans∗=9 1 。那后面的呢？我们到下一层再搞定。下几层的总目标是让 ans = (9^2)^2ans∗=(9 2 ) 2 ，也就是让 ans = 81^2ans∗=81 2 。于是 x = 9*9 = 81x=9∗9=81 且 b = 5 / 2 = 2b=5/2=2。

·第三层循环，b = 2b=2，不是奇数，不着急，只把 81^281 2 当作 (81^2)^1(81 2 ) 1 。下几层的总目标是让 ans = (81^2)^1ans∗=(81 2 ) 1 。于是 x = 81 81 = 6561x=81∗81=6561，b = 2 / 2 = 1b=2/2=1。

·第四层循环，b = 1b=1，是奇数。这时候已经不用看成什么分解了，ans *= 6561ans∗=6561 就可完成总目标。b / 2b/2 为 00。结束循环。

（找不到原文章地址了，发一下大佬博客地址吧QAQ）

引用来自：学委大佬

我在这里完善一下代码，希望大家的思路可以更加清晰一点

#include<iostream>
using namespace std;
long long x,y,m,a,b,ans=1;
int main(){
    cin>>x>>y>>m;
    if(y==0){
        cout<<x<<'^'<<y<<" mod "<<m<<'='<<0;
        return 0;
    }
    a=x;b=y;
    while(b>0){
        if(b&1){
            ans*=a;
            ans%=m;
        }
        a*=a;
        a%=m;
        b/=2;
    }
    cout<<x<<'^'<<y<<" mod "<<m<<'='<<ans;
    return 0;
}