数论入门（python）

一、快速幂

例题&＃xff1a;杭电oj2035

求A^B的最后三位数表示的整数。说明&＃xff1a;A^B的含义是“A的B次方”

由于当b很大时&＃xff0c;时间复杂度高&＃xff0c;所以要快速幂

*关于取模运算的性质&＃xff1a;

(a &＃43; b) % p &＃61; (a % p &＃43; b % p) % p &＃xff08;1&＃xff09;(a - b) % p &＃61; (a % p - b % p ) % p &＃xff08;2&＃xff09;(a * b) % p &＃61; (a % p * b % p) % p &＃xff08;3&＃xff09;

快速幂算法的核心思想就是每一步都把指数分成两半&＃xff0c;而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小&＃xff0c;所需要执行的循环次数也变小&＃xff0c;而最后表示的结果却一直不会变。

​
不是解答&＃xff0c;是我自己随便写的板子a,b&＃61;31,100000
mid&＃61;1 #用来接收盛放奇数幂的底数
mod&＃61;10*8&＃43;9
while b>0:if b%2: #奇数的处理b&＃61;b-1mid&＃61;mid*ab&＃61;b/2a&＃61;a**2%modelse:b &＃61; b / 2 #幂减少一半&＃xff0c;底数翻倍a &＃61; a ** 2 % mod
print(mid*a%mod)​

二、线性筛

原理并不复杂&＃xff0c;但需要看下最后一句

n &＃61; int(input())
st &＃61; [True]*(n&＃43;1)
cnt &＃61; 0
primes &＃61; []
for i in range(2, n&＃43;1):if st[i]:cnt &＃43;&＃61; 1primes.append(i)for p in primes:if i*p>n:break #防止越界st[p*i] &＃61; Falseif i % p &＃61;&＃61; 0:break #这样就保证了每个合数被自己的最小质因数所筛&＃xff0c;不重复&＃xff0c;减少时间复杂度

解释下最后一句&＃xff1a;举个例子 &＃xff1a;i &＃61; 8 p&＃61;2&＃xff0c;如果不跳出循环&＃xff0c;那么再次循环时&＃xff0c;p&＃61;3&＃xff0c;所得的8 * 3  &＃61; 2 * 12&＃xff0c;在i &＃61; 12时会计算再计算一遍24

三、逆元

逆元概念&＃xff1a;在mod某个数意义下的倒数。例如5x≡1&＃xff08;mod3&＃xff09;&＃xff0c;x&＃61;2是满足10&＃61;1&＃xff08;mod3&＃xff09;&＃xff0c;所以称2是5在mod3意义下的逆元。记为inv&＃xff08;a&＃xff0c;p&＃xff09;

需要注意只有a和p互质&＃xff0c;a才有关于p的逆元

四大求逆元的方法

·费马小定理

定理概念&＃xff1a;在p是素数的前提下满足&＃xff1a;

稍作变形&＃xff0c;有&＃xff1a;

即a的p-2次方&＃xff0c;便是我们所求。

a,p&＃61;3,5
#求a mod p 的逆元&＃xff0c;也就是求a的p-2次方
mid&＃61;1
p&＃61;p-2
while p:if p%2:p&＃61;p-1mid&＃61;mid*ap&＃61;p/2a&＃61;a**2continueelse:p &＃61; p / 2a &＃61; a ** 2
print(mid*a)
q&＃61;3*2187
print(q%5)输出&＃xff1a;
2187
1

·欧拉定理

对于素数p&＃xff0c;有&＃xff1a;

其中&＃xff0c;指数是p的欧拉函数值&＃xff0c;也就是小于p的与p互质的数&＃xff08;只有1这一个约数&＃xff09;

类似的变换有&＃xff1a;

对于欧拉函数&＃xff1a;

其中pi是n的所有质因数&＃xff1a;

例如&＃xff1a;φ ( 10 ) 的质因数为2&＃xff0c;5&＃xff0c;所以φ ( 10 ) &＃61; 10 * (1 - 1/2) * (1 - 1/5) &＃61; 4(1,3,5,7这四个数)

φ (24)的质因数为2&＃xff0c;3&＃xff0c;所以φ (24)&＃61;24* (1 - 1/2) * (1 - 1/3)&＃61;8&＃xff08;1,5,7&＃xff0c;11,13,17,19,23这八个数&＃xff09;

欧拉函数性质&＃xff1a;

1&＃xff0c;若n为质数&＃xff0c;则φ ( n ) &＃61; n - 1;
2&＃xff0c;若m与n互质&＃xff0c;则φ ( n*m ) &＃61; φ ( n ) * φ ( m );
3&＃xff0c;若正整数n与a互质&＃xff0c;那么就有&＃xff1a;
4&＃xff0c;若n为奇数时&＃xff0c;φ ( 2n ) &＃61; φ ( n );
5&＃xff0c;若n &＃61; pk且p是质数&＃xff0c;那么φ ( n ) &＃61; (p - 1) * pk-1 &＃61; pk - pk-1.

代码基于快速幂&＃xff0c;不再写了

线性递推求逆元

略

扩展欧几里得求逆元

如果gcd&＃xff08;a&＃xff0c;p&＃xff09;&＃61;1&＃xff1b;
那么就有ax&＃43;py&＃61;1
双方同时modp
就有ax≡1&＃xff08;modp&＃xff09;
因为py是p的倍数全部约掉了
此时x就是a的逆元
所以只需解出该情况下的扩展欧几里得方程的解问题就解决了

def ext_gcd(a,b):if not b :return 1,0,aelse:x,y,gcd&＃61;ext_gcd(b,a%b)x,y&＃61;y,(x-(a//b)*y)return x,y,gcd
x,y,gcd&＃61;ext_gcd(7,6)
print(x,y,gcd)返回值&＃xff1a;
1 -1 1

后续更新&＃xff1a;

扩展欧几里得求ax&＃43;by&＃61;gcd&＃xff08;a&＃xff0c;b&＃xff09;*k

以及通解

四、扩展中国剩余

用于求解模运算方程组&＃xff0c;eg&＃xff1a;

x&＃61;a1∗x1&＃43;b1&＃xff08;1&＃xff09;
x&＃61;a2∗x2&＃43;b2&＃xff08;2&＃xff09;
x&＃61;a2∗x2&＃43;b2&＃xff08;3&＃xff09;

对于一式和二式&＃xff0c;消x得&＃xff1a;

a1*x1&＃43;a2*x2&＃61;b1-b2(因为x是未知量&＃xff0c;符号不考虑&＃xff09;

利用扩展欧几里得求x1&＃xff0c;得到 &＃xff1a;

k&＃61;a1*x1&＃43;b1

于是我们得到新式子&＃xff1a;

x≡k(mod  lcm(a1,a2))

等价于&＃xff1a;x&＃61;lcm(a1,a2)*x&＃39; &＃43;k  (4)

同理联立&＃xff08;3&＃xff09; 和 &＃xff08;4&＃xff09;就能得到解

def ext_gcd(a,b):if not b:x,y&＃61;1,0return x,y,ax,y,gcd&＃61;ext_gcd(b,a%b)x,y&＃61;y,(x-(a//b)*y)return x,y,gcd
n&＃61;3
nums&＃61;[[3,2],[5,3],[7,2]]
while len(nums)>1:mid&＃61;nums.pop()a1,b1&＃61;mid[0],mid[1]mid&＃61;nums.pop()a2, b2 &＃61; mid[0], mid[1]mid1,mid2,mid3&＃61;ext_gcd(a1,a2)q&＃61;abs(b1-b2)mid1,mid2&＃61;mid1*(q/mid3),mid2*(q/mid3)k&＃61;mid1*a1&＃43;b1lcm&＃61;a1*a2/mid3nums.append([lcm,k])
print(int((mid1*a1&＃43;b1)%lcm))