[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加速计算，这里就不演示了。。。

后话

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

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