[A^B%C]简单证明其最大值

命题

给定( A,B,x \in N ),问( A^{x}modB )的最大值。

证明

欧拉定理

欧拉定理的一个结论。

费马小定理

这个比较麻烦,也是欧拉定理的一个特殊情况。

首先假定(A=Bx+y , x,y \in N),则

[ A^{z} = (Bx+y)^{2} ]

通过二项式展开,并且已知( c*B^{x} \% B \equiv 0 , x \geq 1)

则可以知道的是( (y^{x} \% B){max} \equiv (A^{x} \% B){max} ),且y,B互质

费马小定理( y^(B-1)\% B \equiv 1 ),则令( f(x) = y^{x}%B ),则有

( f(0) = 1 ) ( f(B-1) = 1 )

这里使用数学归纳法即可证明出其具有循环节,并且循环节为( B )。

更严格的从欧拉定理出发,这里的循环节准确的来讲是( \phi{B} )。

而这里由于求出欧拉函数( \phi{B} )较为繁琐,所以还是使用时间复杂度为( O(n) )的算法。

代码

原理

很简单,就是直接对B循环内的进行一次遍历即可。

源代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# include <cstdio>
# include <algorithm>
# include <cmath>
using namespace std;
#define max(a, b) (((a) > (b)) ? (a) : (b))
int main()
{
int a,b,res;
long long n;
while (~scanf("%d %d",&a,&b)){
n = 1;
res = -1;
for (int i=0;i<b;i++){
res = max(res,n%b);
n = n*a;// first mi
}
printf("%d\n",res);
}
return 0;
}

这里可以使用空间换时间的方法先计算出( \phi{B} )来降低循环次数,例如:A = 10,B =12时,

此时( \phi{B}=4 ),所以只要计算4次,而不是12次就可以得到结果了。

源代码(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
__author__ = 'kidozh'
# -*- coding: UTF-8 -*-
a = raw_input("A")
b = raw_input("B")
a = int(a)
b = int(b)
res = 0
caculate = 1
for i in range(0,a):
res = max(res,caculate%b)
caculate *=a
print res

也可以使用numpy加速计算,这里就不演示了。。。

后话

有什么问题欢迎评论区指正!

还有就是欧拉定理真是无孔不入。。。