陕西省第一届ACM程序设计竞赛A题(快速幂)

77 阅读 0 评论 51 点赞

我是靠谱客的博主俭朴烤鸡，这篇文章主要介绍陕西省第一届ACM程序设计竞赛A题(快速幂)，现在分享给大家，希望可以做个参考。

http://acm.xidian.edu.cn/land/problem/detail?problem_id=1265

Problem 1265 - A^B % P

Time Limit: 1000MS Memory Limit: 65536KB Difficulty:
Total Submit: 6 Accepted: 4 Special Judge: No

Description

A^B % P is a very interesting problem. Here a more bigger problem needs you to solve.

((((A^B[0])^B[1])^…)^B[n-1])%P

In which B[i]=B[i-1]^2-1( i > 0 ), P=1e9+7

Input

　　The input consists of several test cases.
　　The first line of the input contains a single integer T (0 < T ≤ 20), the number of test cases.
　　Then Followed by T lines, each line gives a test case which contains three integers A, n and B0.
　　0<A<2^31　　0<n<=10000　　1<B[0]<2^31

Output

For each test case, output an integer representing the result of (((A^B[0])^B[1])^…)^B[n-1]%P

Sample Input

2
3 1 2
2 2 2

Sample Output

9
64

分析：

我们知道求解A^B%P，我们可以使用快速幂

指数的运算公式A^B^C=A^(B*C)

费马小定理如果P为素数，A^(P-1)%P=1；

于是运用费马小定理我们就能发现指数B0*B1*B2*…*Bn可以变小为(B0*B1*B2*…*Bn)%(P-1)。

最后我们得出解题步骤

1、用循环求出B1，B2，…，Bn

2、对他们的乘积%(P-1)

3、快速幂求答案

最后程序复杂度为O(N+log(P))

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<string.h>
#include<stdio.h>
#define mod 1000000007
using namespace std;
long long mul(long long a, long long b)
//快速幂求解a^b%mod
{
long long sum =1;
while(b)
{
if(b&1)
sum=sum*a%mod;
a=a*a%mod;
b>>=1;
}
return sum;
}
int main()
{
int c,n,a;
long long m;
scanf("%d",&c);
while (c--)
{
scanf("%d%d%lld",&a,&n,&m);
long long ret = 1;
for (int i=0;i<n;i++)
{
ret=ret*m%(mod-1);
//求出指数的乘积
m=(m*m+mod-2)%(mod-1);
//求出下一个Bi的值
}
a%=mod;
if (a==0)
puts("0");
//如果a=0则直接输出0
else
printf("%lldn", mul(a, ret));
//输出答案
}
return 0;
}