题目描述
对任意正整数 N,计算 XNmod233333 的值。
输入格式
共一行,两个整数 X 和 N。
输出格式
共一行,一个整数,表示 XNmod233333 的值。
数据范围
1≤X,N≤109
样例
输入样例:
2 5
输出样例:
32
算法1
(快速幂) $O(logn)$
时间复杂度
参考文献
python3 代码
MOD = 233333
def quick_mul(x, n) -> int:
res = 1
while n != 0:
if n % 2 == 1:
res = res * x % MOD
x = x * x % MOD
n //= 2
return res
def main():
x, n = map(int, input().split())
res = quick_mul(x, n)
print(res)
if __name__ == '__main__':
main()
C++ 代码
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
const int MOD = 233333;
int quick_mul(long x, int n)
{
long res = 1L;
while (n != 0)
{
if (n % 2 == 1)
{
res = res * x % MOD;
}
x = x * x % MOD;
n >>= 1;
}
return (int)res;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int x; cin >> x;
int n; cin >> n;
int res = quick_mul((long)x, n);
cout << res << endl;
return 0;
}
java 代码
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main
{
static int MOD = 233333;
static long quick_mul(long x, int n)
{
long res = 1L;
while (n != 0)
{
if (n % 2 == 1)
{
res = res * x % MOD;
}
x = x * x % MOD;
n >>= 1;
}
return res;
}
public static void main(String [] args) throws Exception
{
BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
String [] line;
line = BR.readLine().split(" ");
int x = Integer.parseInt(line[0]);
int n = Integer.parseInt(line[1]);
long res = quick_mul(x, n);
System.out.println(res);
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla