memo.day5.RAW | Camber's Logistics | Archive

// C++大法好，我选择Python
// D.R.G. == Delete Rayark Games
没错我说的就是Cytus II

Index:
数论

• 素数
• 欧几里得
• 同余
• 积性函数

Day5/6 / 数论基础

素数 - 筛法判断

1. 埃拉托斯特尼筛法:

   计算整数区间[2，n]中的所有素数的最为简便的筛法
   预处理时间复杂度为O(n * log log n) 空间复杂度为O(n)
   合数是作为素数的倍数被筛去

2. 欧拉筛法:
   (事实上都写的这个)略代码

   # Prime Generator with Euler.
   notPrime = [False]*1000005
   Prime = []
   for i in range(2,1000005):
    if not notPrime[i]: Prime.append(i)
    for ii in Prime:
        if ii == 1: continue
        if i * ii > 1000000: break
        notPrime[i*ii] = True
        if i % ii == 0: break

   概括: 欧拉的原理是遍历+乘

3. 和素数筛相关的不要使用Python(cPython)，会T的飞起，尤其是ZOJ

Goldbach Conjecture

(Link)[localhost]
[-] 待做题 换OJ过了
Python 不适合数据量大的题
你妈的 为什么

题面:

每个大于4的偶数可以写成两个奇素数的和。
例如：8=3+5，3和5都是奇素数；而20=3+17=7+13；42=5+37=11+31=13+29=19+23。
现在哥德巴赫猜想仍然没有被证明是否正确。现在请您证明对所有小于一百万的偶数，哥德巴赫猜想成立

做法
: 预处理 1 - 数据范围 的素数 存入数组

遍历查询是否都为素数

Summation of Four Primes

每个数字是否可以表示成4个素数的总和
[-] Accepted /w c++
[-] Summarize
[ ] Summarize
分析

哥德巴赫猜想的拓展

做法
: (类比于哥德巴赫猜想)预处理

遍历查询

Digit Prime

[-] 所以Python会T飞 && C++ AC
欧拉欧拉欧拉欧拉欧拉欧拉欧拉 (唐突JoJo)
+ 多离线处理一次

素数 - 试除法与Miller-Rabin法(同余)

[ ]待补全

Miller-Rabin

[ ]待补全

PrimeSeq

[ ]待写题

不定方程和同余方程

Background

线性组合: 如果a和b都是整数，则ax+by是a和b的线性组合，其中数x和y是整数
定理
: 如果a和b都是整数，且a和b不全为0

则GCD(a, b) 是a和b的线性组合中最小正整数。

最大公约数和不定方程

####GCD()
代码:

def gcd(a,b):
    return b if a == 0 else gcd(b%a,a)
    # a if b == 0 else gcd(b,a%b)

证明

关键 证明gcd(a,b)与gcd(b%a,a)可互相整除

Happy 2006

如果两个正整数的GCD是1，则称这两个正整数是互素的
要求: 对于给出的整数m，找到按升序排列的第K个和m互素的整数
[ ] 待补完

理解:
本题互质分两类: 小于m的和大于m的
由题解，对其分析

1,3,...,n-1
n+1,n+3,...n-1+n
2n+1,2n+3,...,n-1+2n
...

以此类推，可知其具有周期性
+ 考虑%==0关系 <-> 坑

exGCD()

[ ]待补完
[ ]模逆元

代码 / Reference 数论的编程实验.pptx p34

# Note 模运算的结果一定比双方都小
# 计算量小可以使用python交题
def ext_euclid(a, b):
     if b == 0: return 1, 0, a  #
     else: 
         x, y, q = ext_euclid(b, a % b) # q = gcd(a, b) = gcd(b, a%b)
         # x, y 表示原线性方程的整根
         # 直到递归到达底层前都不会被处理
         x, y = y, (x - (a // b) * y)
         # 
         return x, y, q

定理:

1. 定义: 如果a和b都是整数，则ax+by是a和b的线性组合，其中数x和y是整数
   定理: 如果a和b都是整数，且a和b不全为0，则GCD(a, b) 是a和b的线性组合中最小正整数
   ::即对于ax+by, gcd(a,b)为上式最小值

2. Bezout定理: 如果a和b都是整数，则有整数x和y使得ax+by= GCD(a, b)
   推论: 整数a和b互素当且仅当存在整数x和y使得ax+by=1

3. 模逆元:

4. 定理: 对ax+by=c,设a, b和c都是整数
   如果c不是GCD(a, b)的倍数，则不定方程ax+by=c没有整数解
   如果c是GCD(a, b)的倍数，则不定方程ax+by=c有无穷多整数解

5. 接上: 如果(x0, y0)是ax+by=c的一个整数解
   则ax+by=c的所有整数解是x= x0+ k *(b // GCD(a, b))，y= y0-k *(a // GCD(a, b))，其中k是整数

应用/摘抄:

给出ax+by=c 其中a，b和c是整数常量，x和y是整数变量
要求计算方程的整数根(x, y)
对于不定方程ax+by=c，如果c不是GCD(a, b)的倍数，则不定方程无解
否则扩展的欧几里得算法用于求解。

理解:

1. 在求线性组合ax+by，找a,b的公约数时, 找符合条件的c
2. 对方程 ax+by = gcd(a, b)
   exgcd可以用于求解不定方程的最小整数解 or 判断是否有整数解
   [-]有且只有一个？

The equation

[ ] 不想写，没OJ

同余方程和同余方程组

同余

定义1:

给出一个正整数m和两个整数a和b
如果((a-b) %m)=0，则称a和b模m同余，记为a≡b(%m)。
如果((a-b) %m)!=0，则称a模m不同余于b。

定理:

定理3.2.2.1. 给出一个正整数m和两个整数a和b，((a-b) % m)=0当且仅当(iff)存在整数k,a=b+km
2. 在一个同余式两边同时做加法、减法或乘法，依然保持同余
3. 给出一个正整数m和三个整数a, b和c，a≡b(mod m), 则: a+c≡b+c (mod m); a-c≡b-c (mod m); ac≡bc (mod m)
4.

由上可得出mod法规则:

(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)% p= ((a %p)^b)%p <4>
((a+b)%p+c)%p=(a+(b+c)%p)%p <5>
((ab)%p*c)%p=(a*(bc)%p)%p <6>
交换律<7/8>
((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p <9>

Raising Modulo Numbers / 破OJ 1995

题意: 给出n对数字$A_i$和$B_i$; 以及一个整数M
求解: $(A1^B1+A2^B2+…+An^Bn) mod M$
输入: Z个测试用例 ,

[ ]题解待写
[ ]光靠这题还是搞不懂同余的作用(模法除外)
[-]Accepted

一元线性同余方程

定义3.2.2.2 形如ax≡b(mod m)的同余式被称为一元线性同余方程，
其中a和b是整数，m是正整数，x未知整数

定理3.2.2.4 <!关于解> 对关于x的一元线性同余方程ax≡b(mod m)
设a和b是整数，m是正整数，且GCD(a, m)==d
如果b mod d != 0，则ax≡b(mod m)无解
如果b mod d == 0，则ax≡b(mod m)恰有d个模m不同余的解。

推论3.2.2.3 如果GCD(a, m)=1，则一次同余式ax+b≡0(mod m)有解

由定理 3.2.2.4，对于一元线性同余方程ax≡b(mod m)，计算x的算法如下
步骤1：应用欧几里得算法和扩展的欧几里得算法分别计算d=GCD(a, m)和d=ax’+my’的解(x’, y’)，其中x’是ax’≡d(mod m)的解 <= gcd(a,m)=ax’+my’
步骤2：如果b mod d!=0，则ax≡b(mod m)无解；
否则存在d个模m不同余的解，其中第一个解$x0=x’*(b DIV d) mod m$
其余的d-1解是$xi=(x0+i*(m DIV d)) mod m，1≤i≤d-1$

C Looooooooooooops

有关同余关系的实验
题面: POJ 2115

给出了一个C语言风格类型的循环：

for(variable = A; variable != B; variable += C)
      statement;

即一个循环(中略)我们要知道语句执行多少次，本题设定所有的算术运算都是在以2k为模的k位无符号整数类型（值0 ≤ x<2k）上进行。

[ ]同余关系 理解不能

同余方程组

中国剩余定理

特殊的同余式

威尔逊定理和费马小定理

引理1:

p是素数，正整数a是其自身模p的逆当且仅当a≡1(mod p)或a≡-1(mod p)
[ ]证明 待补全

威尔逊定理:

如果p是素数，则(p-1)!≡-1(mod p)
== 若p为质数，则p可整除(p-1)!+1

YAPTCHA

// 原题解析有问题

---

费马小定理

如果p是素数，a是正整数，且GCD(a, p)=1，则a^(p-1)≡1 (mod p)
==>若p为质数&&a,b互质, 则p可整除

What day is that day

伪素数

欧拉定理 / P106

定义3.3.3.1: 设n是一个正整数。欧拉𝜑函数$𝜑(n)$是不超过n且与n互素的正整数的个数
定义3.3.3.2: 模n的既约剩余系是由$𝜑(𝑛)$个整数构成的集合，集合中的每个元素均与n*互素***，且任何两个元素模n不同余。
理解:

定理3.3.1: pass
定理3.3.5/欧拉定理: 若n和a互素且为正整数，则$a^(𝜑(𝑛))≡1(mod n)$
推论3.3.1: 若n和a互素且为正整数，则$a^(𝜑(𝑛)+1)≡a(mod n)$

积性函数

欧拉函数

定义3.4.1/算术函数: 所有在正整数上运算的函数都被称为算术函数
定义3.4.2/积性函数:

如果算术函数f对任意两个互素的正整数a和b，f(𝑎𝑏)=𝑓(𝑎)𝑓(𝑏)，则f被称为积性函数（或乘性函数）
如果对任意两个正整数a和b，f(𝑎𝑏)=𝑓(𝑎)𝑓(𝑏)，则f被称为完全积性函数（或完全乘性函数）(和上面的不同是没有对互素的要求)

由上:
定理3.4.1

如果f是一个积性函数, n是一个正整数, 且n有素幂因子分解n = (p_1)^(a_1)(p_2)^(a_2)…(p_m)^(a_m)
则f(n) = f((p_1)^(a_1))f((p_2)^(a_2))..f((p_m)^(a_m))

定义3.4.3 欧拉函数 见上 + 欧拉函数是一个积性函数
定理3.4.2 若a是素数 𝜑(𝑛)=n-1 否则𝜑(𝑛) < n-1
定理3.4.3 𝜑函数公式:

---

---

Relatives

Primitive Roots

莫比乌斯

Sky Code

+容斥原理

除非另有说明皆以CC BY-SA 4.0发布
本文链接：https://logistics.camber.moe/2019/memo-day5-RAW/