Posted in日常

P1226-快速幂

2024年4月11日

题目传送门

点我

题目思路

题目本身是分治思想做，通过利用mod操作的分配率来做：

(a*b)mod p=(a mod p * b mod p)mod p

然后通过将指数来分治最后合并，初代代码如下：

#include <iostream>
#include <math.h>

using namespace std;

int fz(long long a, long long b, long long p)
{
    long long ans = 1;
    if (b == 1)
        return a % p;
    long long ans1 = fz(a, b / 2, p);
    long long ans2 = fz(a, b - b / 2, p);
    ans = (ans1 * ans2) % p;
    return ans;
}

int main()
{
    long long a, b, p;
    cin >> a >> b >> p;
    string ans = "";
    ans += to_string(a);
    ans += "^";
    ans += to_string(b);
    ans += " mod ";
    ans += to_string(p);
    ans += "=";
    if (b == 0)
        ans += "1";
    else
        ans += to_string(fz(a, b, p));
    cout << ans << endl;
    return 0;
}

思路是对的，可惜TLE了，淦。

但是还不够快，快，战斗，爽！

走错频道了，显然要用更快的方法。

首先是快速幂的做法

就是将a^b中的b转换为二进制列，如11=1011，那么a^11=a^8*a^2*a^1。

于是就可以操作;

base=a,ans=1。

每次将b&1，如果为1，说明最低位是1，ans需要乘上base

然后base自乘，相当于二进制位的前一位

然后b右移一位，不断循环

最后注意，对于mod运算，直接将ans和base在每一步后都mod就可以了，最后再mod一次即可

AC代码

#include <iostream>
#include <math.h>

using namespace std;

int main()
{
    long long a, b, p;
    cin >> a >> b >> p;
    string ans = "";
    ans += to_string(a);
    ans += "^";
    ans += to_string(b);
    ans += " mod ";
    ans += to_string(p);
    ans += "=";
    if (b == 0)
        ans += "1";
    else
    {
        long long pp = 1;
        long long base = a;
        while (b > 0)
        {
            if (b & 1 == 1)
            {
                pp = (pp * base) % p;
            }
            base *= base;
            base %= p;
            b >>= 1;
            pp %= p;
        }
        ans += to_string(pp);
    }
    cout << ans << endl;
    return 0;
}
Tags: