acwing每日一题-1

发表于 更新于 分类于 阅读次数： 本文字数： 663 阅读时长 ≈ 1 分钟
acwing每日一题——幂次方

题目

对任意正整数N, 计算 XN mod 233333 的值。

输入格式

共一行，两个整数 X 和 N。

输出格式

共一行，一个整数，表示XN mod 233333的值。

数据范围

1$\leq$ X , N$\leq$ 109

输入样例

1
2 5

输出样例

1
32
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int quick_power(int a, int k, int p)
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int main()
{
    int x,y;
    cin>>x>>y;
    cout<<quick_power(x,y,233333);
}
解法

快速幂模板：

1
2
3
4
5
6
7
8
9
10
11
int quick_power(int a, int k, int p)  // 求a^k mod p
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;  //当k末位为1时
        a = (LL)a * a % p;  //a平方更新
        k >>= 1;  //k右移一位
    }
    return res;
}