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

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

程序员文章站 2022-03-03 08:52:47
...
  • 1.题目分析

原题

本题在于快速幂的使用,以及对long long的应用问题。

  • 2.解题思路
  1. 快速幂

求幂常见用法:

int pow(int a,int b) {
    int ans;
    for(int i = 1;i<=b;++i) {
        ans*=a;
    }
    return ans;
}

原理十分简单,将a乘b次。 时间复杂度: O(n)

但快速幂比它更快:

while(m>0){
        if(m%2==1)
            ans=ans*b%p;
        b=b*b%p;
        m=m>>1;
}

(以上是算法示例) 时间复杂度: O(log n)

所以,代码就出来了:

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main() {
    long long ans = 1, i, j, k, m, n, b, p;
    scanf_s("%lld%lld%lld", &b, &m, &p);
    printf("%lld^%lld mod %lld=", b, m, p);
    while (m > 0) {
        if (m % 2 == 1)
            ans = ans * b % p;
        b = b * b % p;
        m = m >> 1;
    }
    printf("%lld", ans % p);
    return 0;
}