例题：杭电oj2035
求A^B的最后三位数表示的整数。说明：A^B的含义是“A的B次方”
由于当b很大时，时间复杂度高，所以要快速幂
*关于取模运算的性质：
(a + b) % p = (a % p + b % p) % p （1） (a - b) % p = (a % p - b % p ) % p （2） (a * b) % p = (a % p * b % p) % p （3）
快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。
不是解答，是我自己随便写的板子
a,b=31,100000
mid=1 #用来接收盛放奇数幂的底数
mod=10*8+9
while b>0:
if b%2: #奇数的处理
b=b-1
mid=mid*a
b=b/2
a=a**2%mod
else:
b = b / 2 #幂减少一半，底数翻倍
a = a ** 2 % mod
print(mid*a%mod)
二、线性筛
原理并不复杂，但需要看下最后一句
n = int(input())
st = [True]*(n+1)
cnt = 0
primes = []
for i in range(2, n+1):
if st[i]:
cnt += 1
primes.append(i)
for p in primes:
if i*p>n:break #防止越界
st[p*i] = False
if i % p == 0:break #这样就保证了每个合数被自己的最小质因数所筛，不重复，减少时间复杂度
解释下最后一句：举个例子 ：i = 8 p=2，如果不跳出循环，那么再次循环时，p=3，所得的8 * 3 = 2 * 12，在i = 12时会计算再计算一遍24
三、逆元逆元概念：在mod某个数意义下的倒数。例如5x≡1（mod3），x=2是满足10=1（mod3），所以称2是5在mod3意义下的逆元。记为inv（a，p）
需要注意只有a和p互质，a才有关于p的逆元
四大求逆元的方法
·费马小定理定理概念：在p是素数的前提下满足：
稍作变形，有：
即a的p-2次方，便是我们所求。
a,p=3,5
#求a mod p 的逆元，也就是求a的p-2次方
mid=1
p=p-2
while p:
if p%2:
p=p-1
mid=mid*a
p=p/2
a=a**2
continue
else:
p = p / 2
a = a ** 2
print(mid*a)
q=3*2187
print(q%5)
输出：
2187
1
·欧拉定理
对于素数p，有：
其中，指数是p的欧拉函数值，也就是小于p的与p互质的数（只有1这一个约数）
类似的变换有：
对于欧拉函数：其中pi是n的所有质因数：
例如：φ ( 10 ) 的质因数为2，5，所以φ ( 10 ) = 10 * (1 - 1/2) * (1 - 1/5) = 4(1,3,5,7这四个数)
φ (24)的质因数为2，3，所以φ (24)=24* (1 - 1/2) * (1 - 1/3)=8（1,5,7，11,13,17,19,23这八个数）
欧拉函数性质：1，若n为质数，则φ ( n ) = n - 1;
2，若m与n互质，则φ ( n*m ) = φ ( n ) * φ ( m );
3，若正整数n与a互质，那么就有：
4，若n为奇数时，φ ( 2n ) = φ ( n );
5，若n = pk且p是质数，那么φ ( n ) = (p - 1) * pk-1 = pk - pk-1.
代码基于快速幂，不再写了
线性递推求逆元略
扩展欧几里得求逆元如果gcd（a，p）=1；
那么就有ax+py=1
双方同时modp
就有ax≡1（modp）
因为py是p的倍数全部约掉了
此时x就是a的逆元
所以只需解出该情况下的扩展欧几里得方程的解问题就解决了
def ext_gcd(a,b):
if not b :
return 1,0,a
else:
x,y,gcd=ext_gcd(b,a%b)
x,y=y,(x-(a//b)*y)
return x,y,gcd
x,y,gcd=ext_gcd(7,6)
print(x,y,gcd)
返回值：
1 -1 1
后续更新：
扩展欧几里得求ax+by=gcd（a，b）*k
以及通解
四、扩展中国剩余用于求解模运算方程组，eg：
x=a1∗x1+b1（1） x=a2∗x2+b2（2） x=a2∗x2+b2（3）
对于一式和二式，消x得：
a1*x1+a2*x2=b1-b2(因为x是未知量，符号不考虑）
利用扩展欧几里得求x1，得到 ：
k=a1*x1+b1
于是我们得到新式子：
x≡k(mod lcm(a1,a2))
等价于：x=lcm(a1,a2)*x' +k (4)
同理联立（3） 和 （4）就能得到解
def ext_gcd(a,b):
if not b:
x,y=1,0
return x,y,a
x,y,gcd=ext_gcd(b,a%b)
x,y=y,(x-(a//b)*y)
return x,y,gcd
n=3
nums=[[3,2],[5,3],[7,2]]
while len(nums)>1:
mid=nums.pop()
a1,b1=mid[0],mid[1]
mid=nums.pop()
a2, b2 = mid[0], mid[1]
mid1,mid2,mid3=ext_gcd(a1,a2)
q=abs(b1-b2)
mid1,mid2=mid1*(q/mid3),mid2*(q/mid3)
k=mid1*a1+b1
lcm=a1*a2/mid3
nums.append([lcm,k])
print(int((mid1*a1+b1)%lcm))
