珠海 网站开发,怎么把百度到自己的网站,网站后台不能编辑,设计网站页面的工作叫啥打死没想到会在H老师处学懂数论同余#xff0c;整除模运算埃式筛法欧拉筛法最大公约数和最小公倍数辗转相除法更相减损术裴蜀定理威尔逊定理费马定理同余等价类、剩余系、缩系欧拉函数欧拉定理扩展欧拉定理区间逆元扩展欧几里得中国剩余定理扩展中国剩余定理利用以上所有知识进…
打死没想到会在H老师处学懂数论同余整除模运算埃式筛法欧拉筛法最大公约数和最小公倍数辗转相除法更相减损术裴蜀定理威尔逊定理费马定理同余等价类、剩余系、缩系欧拉函数欧拉定理扩展欧拉定理区间逆元扩展欧几里得中国剩余定理扩展中国剩余定理利用以上所有知识进行证明同余整除
整除的性质 传递性若a∣b,b∣ca|b,b|ca∣b,b∣c则a∣ca|ca∣ca∣b,a∣ca|b,a|ca∣b,a∣c等价于对于任意的整数x,yx,yx,y有a∣(bxcy)a|(bxcy)a∣(bxcy)设m≠0m≠0m0则a∣ba|ba∣b等价于ma∣mbma|mbma∣mb设整数x,yx,yx,y满足axby1,a∣n,b∣,naxby1,a|n,b|,naxby1,a∣n,b∣,n则(ab)∣n(ab)|n(ab)∣n若bq∗dcbq*dcbq∗dc则d∣bd|bd∣b的充要条件是d∣cd|cd∣c 同余的性质 同加性若a≡b(modp)a\equiv b(mod\ p)a≡b(mod p)则ac≡bc(modp)ac\equiv bc(mod\ p)ac≡bc(mod p)同减性若a≡b(modp)a\equiv b(mod\ p)a≡b(mod p)则a−c≡b−c(modp)a-c\equiv b-c(mod\ p)a−c≡b−c(mod p)同乘性若a≡b(modp)a\equiv b(mod\ p)a≡b(mod p)则a×c≡b×c(modp)a\times c\equiv b\times c(mod\ p)a×c≡b×c(mod p)同除性若a≡b(modp),c∣a,c∣b,(c,p)1a\equiv b(mod\ p),c|a,c|b,(c,p)1a≡b(mod p),c∣a,c∣b,(c,p)1则a/c≡b/c(modp)a/c\equiv b/c(mod\ p)a/c≡b/c(mod p)同幂性若a≡b(modp),c0a\equiv b(mod\ p),c0a≡b(mod p),c0则ac≡bc(modp)a^c\equiv b^c(mod\ p)ac≡bc(mod p)若a%px,a%qx,(p,q)1a\% px,a\% qx,(p,q)1a%px,a%qx,(p,q)1则a%(p∗q)xa\% (p*q)xa%(p∗q)x 数论常识 若2能整除a的最末位则2∣a2|a2∣a若4能整除a的末两位则4∣a4|a4∣a若8能整除a的末三位则8∣a8|a8∣a若3能整除a的各位数字之和则3∣a3|a3∣a若9能整除a的各位数字之和则9∣a9|a9∣a若11能整除a的偶数位数字之和与奇数位数字之和的差则11∣a11|a11∣a能被7,11,137,11,137,11,13整除的数的特征是这个数的末三位与末三位以前的数字所组成数之差能被7,11,137,11,137,11,13整除 模运算
1.分配率 (ab)%c(a%cb%c)%c(ab)\% c(a\% cb\% c)\% c(ab)%c(a%cb%c)%c(a−b)%c(a%c−b%c)%c(a-b)\% c(a\% c-b\% c)\% c(a−b)%c(a%c−b%c)%c(a×b)%c(a%c×b%c)%c(a\times b)\% c(a\% c\times b\% c)\% c(a×b)%c(a%c×b%c)%c(ab)%c(a%c)b%c(a^b)\% c(a\% c)^b\% c(ab)%c(a%c)b%c 2.放缩性 如果a%bc,d≠0a\% bc,d≠0a%bc,d0则有(a×d)%(b×d)c×d(a\times d)\%(b\times d)c\times d(a×d)%(b×d)c×d如果a%bc,d∣a,d∣ba\%bc,d\bigg|a,d\bigg|ba%bc,d∣∣∣∣a,d∣∣∣∣b则(a/d)%(b/d)(c/d)(a/d)\%(b/d)(c/d)(a/d)%(b/d)(c/d) 根据放缩性则除法取余有式子 a/b%ca%(b×c)/ba/b\%ca\%(b\times c)/ba/b%ca%(b×c)/b 埃式筛法
先把nnn以内的222的倍数(不包含222)全部删除再把nnn以内的333的倍数(不包含333)全部删除…
这样做下去最后剩下的以内的数全为质数
这里的删除其实不是真的删除只是打上一个删除标记而已
每个数都会被它的质因子打一次标记而一个数的不同的质因子个数不超过logNlogNlogN
所以时间复杂度为O(NlogN)O(NlogN)O(NlogN)
void getprime( int n ) {for( int i 2;i n;i ) {if( flag[i] ) continue;prime[ cnt] i;for( int j i;j n / i;j )flag[j * i] 1;}
}欧拉筛法
在上述的埃氏筛法中一个数可能被它的各个质因子都筛了一遍
而一个数的质因子种类数是不会超过logNlogNlogN的,所以时间复杂度为O(NlogN)O(NlogN)O(NlogN)
而欧式筛法保证每个数只被它的最小质因子筛一遍这样时间复杂度便降成了O(N)O(N)O(N) 有一个质数集合SSS一开始质数集合为空
同时有一个boolboolbool数组flagflagflag表示删除标记
有两层循环
外层循环从222开始枚举倍数设当前枚举的量为aaa
如果aaa是质数则将aaa加入质数集合
内层循环枚举质数集合中的元素将数组中它们的aaa倍全部打上删除标记
显然未打删除标记的数都是质数了flagflagflag数组中下标小于222的元素是无效的不用考虑
但现在的时间复杂度仍然是O(NlogN)O(NlogN)O(NlogN)的接下来要用一个优化来完成O(N)O(N)O(N)的蜕变
设当前倍数为aaa在内层循环中设当前枚举到集合SSS中的第iii个质数pip_ipi
先将i∗pii*p_ii∗pi打上标记
如发现iii是pip_ipi的倍数时
此时后续的质数就无需再枚举了可以提前退出内层循环
外层循环处理下一轮即aaa 为什么满足这种条件就可以提前breakbreakbreak呢
设后续的质数为pi′p_ipi′而pi′pip_ip_ipi′pi
因为aaa是pip_ipi的倍数那么a×pi′a\times p_ia×pi′也是pip_ipi的倍数
设a×pi′b×pia\times p_ib\times p_ia×pi′b×pi
∵pi′pi∵p_ip_i∵pi′pi
∴ba∴ba∴ba
我们希望每个数被它的最小质因子给删掉
所以a×pi′a\times p_ia×pi′应该被pip_ipi删掉就要求a×pi′/pia\times p_i/p_ia×pi′/pi尽量大
所以后续所有的质数就都留给倍数aaa增长到bbb再去处理了 void sieve( int n ) {for( int i 2;i n;i ) {if( ! flag[i] ) prime[ cnt] i;for( int j 1;j cnt i * prime[j] n;j ) {flag[i * prime[j]] 1;if( i % prime[j] 0 ) break;}}
}最大公约数和最小公倍数 gcd(a,b)×lcm(a,b)a∗bgcd(a,b)\times lcm(a,b)a*bgcd(a,b)×lcm(a,b)a∗b 证明 将a,ba,ba,b进行质因子分解设a,ba,ba,b的质因子集合并集为p1,p2,p3...pkp_1,p_2,p_3...p_kp1,p2,p3...pk 设ap1i1p2i2...pkik,(0≤i1,0≤i2...0≤ik)设ap_1^{i_1}p_2^{i_2}...p_k^{i_k},(0≤i_1,0\le i_2...0\le i_k)设ap1i1p2i2...pkik,(0≤i1,0≤i2...0≤ik) 设bp1j1p2j2...pkjk,(0≤j1,0≤j2...0≤jk)设bp_1^{j_1}p_2^{j_2}...p_k^{j_k},(0\le j_1,0\le j_2...0\le j_k)设bp1j1p2j2...pkjk,(0≤j1,0≤j2...0≤jk) gcd(a,b)p1min(i1,j1)p2min(i2,j2)...pkmin(ik,jk)gcd(a,b)p_1^{min(i_1,j_1)}p_2^{min(i_2,j_2)}...p_k^{min(i_k,j_k)}gcd(a,b)p1min(i1,j1)p2min(i2,j2)...pkmin(ik,jk) lcm(a,b)p1max(i1,j1)p2max(i2,j2)...pkmax(ik,jk)lcm(a,b)p_1^{max(i_1,j_1)}p_2^{max(i_2,j_2)}...p_k^{max(i_k,j_k)}lcm(a,b)p1max(i1,j1)p2max(i2,j2)...pkmax(ik,jk) ∵min(it,jt)max(it,jt)itjt∵min(i_t,j_t)max(i_t,j_t)i_tj_t∵min(it,jt)max(it,jt)itjt ∴gcd(a,b)lcm(a,b)p1i1j1p2i2j2...pkikjk∴gcd(a,b)lcm(a,b)p_1^{i_1j_1}p_2^{i_2j_2}...p_k^{i_kj_k}∴gcd(a,b)lcm(a,b)p1i1j1p2i2j2...pkikjk 辗转相除法 gcd(a,b)≡gcd(b,a%b)gcd(a,b)\equiv gcd(b,a\%b)gcd(a,b)≡gcd(b,a%b) 证明 设dgcd(a,b),ax∗d,by∗ddgcd(a,b),ax*d,by*ddgcd(a,b),ax∗d,by∗d
根据模运算的放缩性有a%b(x∗d)%(y∗d)(x%y)∗da\%b(x*d)\%(y*d)(x\%y)*da%b(x∗d)%(y∗d)(x%y)∗d
∵(x,y)1∵(x,y)1∵(x,y)1
∴(y,x%y)1∴(y,x\%y)1∴(y,x%y)1
int gcd( int x, int y ) {if( ! y ) return x;else return gcd( y, x % y );
}时间复杂度O(log)O(\log)O(log)最坏情况就是斐波拉契数列相当于相邻两位一位一位移动辗转相减
辗转相减法 gcd(a,b)gcd(b,a−b),abgcd(a,b)gcd(b,a-b),abgcd(a,b)gcd(b,a−b),ab 证明
令aAd,bBd,(A,B)1→(a,b)daAd,bBd,(A,B)1\rightarrow (a,b)daAd,bBd,(A,B)1→(a,b)d
则a−b(A−B)da-b(A-B)da−b(A−B)d
若gcd(b,a−b)gcd(Bd,(A−B)d)≠dgcd(b,a-b)gcd\bigg(Bd,(A-B)d\bigg)≠dgcd(b,a−b)gcd(Bd,(A−B)d)d
说明gcd(B,A−B)1gcd(B,A-B)1gcd(B,A−B)1
令gcd(B,A−B)g,Bsg,A−Btggcd(B,A-B)g,Bsg,A-Btggcd(B,A−B)g,Bsg,A−Btg
则一定有g∣Ag\bigg|Ag∣∣∣∣A
与(A,B)1(A,B)1(A,B)1矛盾所以gcd(B,A−B)1gcd(B,A-B)1gcd(B,A−B)1 更相减损术 若约分ab\frac{a}{b}ba 如a,ba,ba,b均为偶可先将a,ba,ba,b折半即/2/2/2 否则将a,ba,ba,b交替的减去对方 直到最后两数相等此时的数乘上先前除掉的222即为原来a,ba,ba,b的最大公约数 裴蜀定理 如果a,ba,ba,b的最大公约数为ddd且d∣cd\bigg|cd∣∣∣∣c则存在整数x,yx,yx,y使得axbycaxbycaxbyc 证明
转化证明存在x,yx,yx,y使得axbydaxbydaxbyd
假设存在这样一对x,yx,yx,y那么只需将其进行倍数放缩即可
∵(a,b)d∵(a,b)d∵(a,b)d
∴∴∴设a′a/d,b′b/daa/d,bb/da′a/d,b′b/d
则有a′xb′y1,(a′,b′)1axby1,(a,b)1a′xb′y1,(a′,b′)1
证明转化为 求一对x,yx,yx,y使得a′xb′y1axby1a′xb′y1且满足(a′,b′)1(a,b)1(a′,b′)1
即求证a′x%b′1ax\%b1a′x%b′1感性理解若干倍的a′aa′减去若干倍的b′bb′等于111 引理一 如果a,ba,ba,b为正整数且a,ba,ba,b互质则不存在小于bbb的正整数kkk使得0≡k∗a(modb)0\equiv k*a(mod\ b)0≡k∗a(mod b) 证明
用反证法即可假设存在这样的一个kkk使得该式成立
则需满足kkk或者aaa能整除bbb
∵(a,b)1∵(a,b)1∵(a,b)1
∴a∴a∴a不可能整除bbb
∵0kb∵0kb∵0kb
∴k∴k∴k亦不可能整除bbb 推论 如果a,ba,ba,b为正整数且a,ba,ba,b互质则0,a,a∗2,a∗3...(b−1)∗a0,a,a*2,a*3...(b-1)*a0,a,a∗2,a∗3...(b−1)∗a这些数取模bbb余数互不相等 证明
反证法
设存在0ijb0ijb0ijb使得a∗i≡a∗j(modb)a*i\equiv a*j(mod\ b)a∗i≡a∗j(mod b)
则有(i−j)∗a≡0(modb)(i-j)*a\equiv 0(mod\ b)(i−j)∗a≡0(mod b)
同理引理一i−j,ai-j,ai−j,a都不可能整除bbb故与假设矛盾不成立 引理二 如果(a,b)1(a,b)1(a,b)1则必存在一个整数kkk满足k∗a%b1k*a\% b1k∗a%b1 证明 根据上面推论易知这些数取模bbb的值只会在区间[0,b−1][0,b-1][0,b−1]k0k0k0时取模余数为000
而且各不相同其中一定存在取模后的余数为111的值 根据引理二可知 如果(a,b)1(a,b)1(a,b)1则必存在一个整数kkk满足k∗a%b1k*a\% b1k∗a%b1
即k∗a−p∗b1k*a-p*b1k∗a−p∗b1裴蜀定理得证 威尔逊定理 (p−1)!≡−1(modp)(p-1)!\equiv -1(mod\ p)(p−1)!≡−1(mod p)当且仅当ppp为质数 证明
先证充分性→p\rightarrow p→p为质数有(p−1)!≡p−1(modp)(p-1)!\equiv p-1(mod\ p)(p−1)!≡p−1(mod p)
假设0ip0ip0ip根据上面的裴蜀定理可得(i,p)1(i,p)1(i,p)1且必存在一个整数j(0jp)j(0jp)j(0jp)
使得i×j%p1i\times j\%p1i×j%p1即jjj是iii的逆元由此可见逆元具有唯一性相互性
所以在[1,p−1][1,p-1][1,p−1]中逆元是一对一对的
然而……也有可能存在iii的逆元是本身的那么此时的iii就要满足以下条件
i2%p1⇒(i1)(i−1)%p0i^2\%p1\Rightarrow (i1)(i-1)\%p0i2%p1⇒(i1)(i−1)%p0
∴i10∴i10∴i10或pppi−10i-10i−10或ppp
∵0ip∵0ip∵0ip
∴i1p,i−10∴i1p,i-10∴i1p,i−10
即ip−1,1ip-1,1ip−1,1
每一对逆元取模ppp都为111需要证明的原式变成1∗p−1≡p−1(modp)1*p-1\equiv p-1(mod\ p)1∗p−1≡p−1(mod p)
显然成立证毕 再证必要性→(p−1)!≡p−1(modp)\rightarrow (p-1)!\equiv p-1(mod\ p)→(p−1)!≡p−1(mod p)当该式成立时ppp一定为质数
反证法即证明ppp不为质数时该式不成立
如ppp不为质数则[2,p−1][2,p-1][2,p−1]中一定有ppp的因子设为iii则i,p/ii,p/ii,p/i均为ppp的因子 若i≠p/ii≠p/iip/i则1×2×3×...×(p−1)1\times 2\times 3\times ...\times (p-1)1×2×3×...×(p−1)一定是ppp的倍数取模ppp为000 若ip/iip/iip/i则1×2×3×...×(p−1)1\times 2\times 3\times ...\times (p-1)1×2×3×...×(p−1)一定是iii的倍数模ppp必为iii的倍数 又因为ppp是iii的倍数且i1i1i1所以p−1p-1p−1不可能是iii的倍数所以(p−1)!≡−1(modp)(p-1)!\equiv-1(mod\ p)(p−1)!≡−1(mod p) 费马定理 如果ppp为质数且a%p≠0a\%p≠0a%p0则有ap−1%p1a^{p-1}\%p1ap−1%p1 证明 (a∗1)∗(a∗2)∗...∗(a∗(p−1))ap−1∗(p−1)!(modp)(a*1)* (a* 2)* ...*(a* (p-1))a^{p-1}*(p-1)!\ \ (mod\ p)(a∗1)∗(a∗2)∗...∗(a∗(p−1))ap−1∗(p−1)! (mod p) ∵(a,p)1∵(a,p)1∵(a,p)1 ∴{(a∗1)%p,(a∗2)%p,...,(a∗(p−1))%p}{1,p−1}∴\{(a* 1)\% p,(a*2)\% p,...,(a*(p-1))\%p\}\{1,p-1\}∴{(a∗1)%p,(a∗2)%p,...,(a∗(p−1))%p}{1,p−1} 即取模后的值互不相等且∈[1,p−1]∈[1,p-1]∈[1,p−1] ∴(a∗1)%p,(a∗2)%p,...,(a∗(p−1))%p(p−1)!(modp)∴(a*1)\% p,(a*2)\% p,...,(a*(p-1))\%p(p-1)!\ \ (mod\ p)∴(a∗1)%p,(a∗2)%p,...,(a∗(p−1))%p(p−1)! (mod p) (p−1)!ap−1(p−1)!(modp)(p-1)!a^{p-1}(p-1)!\ \ (mod\ p)(p−1)!ap−1(p−1)! (mod p) ∴ap−11(modp)∴a^{p-1}1\ \ (mod\ p)∴ap−11 (mod p) 同余等价类、剩余系、缩系 对于一个正整数ppp所有非负整数模ppp的结果只有ppp种可能即{0,1,2,...,p−1}\{0,1,2,...,p-1\}{0,1,2,...,p−1} 模ppp的剩余系指的是{0,1,2,...,p−1}\{0,1,2,...,p-1\}{0,1,2,...,p−1}即小于ppp的所有非负整数这个集合中包含了所有模ppp的余数 模ppp的剩余系记为ZpZ_pZp 剩余系中每一个元素代表的是一类数 比如在剩余系ZpZ_pZp中 000表示的是所有模ppp为000的数即{0,p,2p,3p...}\{0,p,2p,3p...\}{0,p,2p,3p...}111表示的是所有模ppp为111的数即{1,p1,2p1,3p1...}\{1,p1,2p1,3p1...\}{1,p1,2p1,3p1...} 这些模ppp余数相同的数称为同余等价类 可以发现在模意义下所有的非负整数可以被分为若干同余等价类 如果我们只考虑剩余系中与模数p互质的数便得到一个子集称为模p的缩系记为Zp∗Z_p^*Zp∗ 如ppp为666则Zp∗{1,5}Z_p^*\{1,5\}Zp∗{1,5} 缩系又称为简化剩余系 欧拉函数
欧拉函数即为缩系的大小 ϕ(1)1\phi(1)1ϕ(1)1 如果nnn为质数则ϕ(n)n−1\phi(n)n-1ϕ(n)n−1如果napna^pnap且aaa为质数则ϕ(n)ap−ap−1ap(1−1a)\phi(n)a^p-a^{p-1}a^p(1-\frac{1}{a})ϕ(n)ap−ap−1ap(1−a1)令na1p1a2p2...akpkna_1^{p_1}a_2^{p_2}...a_k^{p_k}na1p1a2p2...akpk根据积性函数性质 ϕ(n)ϕ(a1p1)ϕ(a2p2)...ϕ(akpk)a1p1(1−1a1)∗a2p2(1−1a2)...akpk(1−1ak)\phi(n)\phi(a_1^{p_1})\phi(a_2^{p_2})...\phi(a_k^{p_k})a_1^{p_1}(1-\frac{1}{a_1})*a_2^{p_2}(1-\frac{1}{a_2})...a_k^{p_k}(1-\frac{1}{a_k})ϕ(n)ϕ(a1p1)ϕ(a2p2)...ϕ(akpk)a1p1(1−a11)∗a2p2(1−a21)...akpk(1−ak1) n∗(1−1a1)∗(1−1a2)∗...∗(1−1ak)n*(1-\frac{1}{a_1})*(1-\frac{1}{a_2})*...*(1-\frac{1}{a_k})n∗(1−a11)∗(1−a21)∗...∗(1−ak1) ∑d∣nϕ(d)n\sum_{d\big|n}\phi(d)nd∣∣n∑ϕ(d)n 考虑用分数形式证明
nnn个真分数1n,2n,...,n−1n,nn\frac{1}{n},\frac{2}{n},...,\frac{n-1}{n},\frac{n}{n}n1,n2,...,nn−1,nn
然后进行分数化简按分母不同分类
分母一定是nnn的因数且分母分子互质并且真分数形式的分子小于分母
那么该类分数个数就是分母的ϕ\phiϕ得证 小于nnn且与nnn互质的所有正整数之和为nϕ(n)2\frac{n\phi(n)}{2}2nϕ(n) 证明 设s{a1,a2,...,ak}s\{a_1,a_2,...,a_k\}s{a1,a2,...,ak}是在模nnn意义下的缩系根据缩系定义个数就是ϕ(n)\phi(n)ϕ(n)
则t{n−a1,n−a2,...,n−ak}t\{n-a_1,n-a_2,...,n-a_k\}t{n−a1,n−a2,...,n−ak}也是模nnn意义下的缩系详见辗转相除法的辗转相减
两个集合相加证毕
//求单个phi(n)
int getphi( int x ) {int ans x;for( int i 2;i * i x;i ) {if( x % i 0 ) {ans ans / i * ( i - 1 );while( x % i 0 ) x / i;}}if( x 1 ) ans ans / x * ( x - 1 );return ans;
}//求多个phi(n)
void getphi( int n ) {for( int i 2;i n;i ) {if( ! phi[i] ) {phi[i] i - 1;for( int j i 1;j n;j i ) {if( ! phi[j] ) phi[j] j;phi[j] phi[j] / i * ( i - 1 );}}}
}欧拉定理 如果(a,p)1(a,p)1(a,p)1则aϕ(p)≡1(modp)a^{\phi(p)}\equiv1(mod\ p)aϕ(p)≡1(mod p) 证明
设ppp的简化剩余系为{p1,p2,p3,...,pk}\{p_1,p_2,p_3,...,p_k\}{p1,p2,p3,...,pk}
∵(a,p)1∵(a,p)1∵(a,p)1
∴{a∗p1,a∗p2,...,a∗pk}∴\{a*p_1,a*p_2,...,a*p_k\}∴{a∗p1,a∗p2,...,a∗pk}也构成了ppp的简化剩余系
证明可参考裴蜀定理中的推论反证法
∴(a∗p1)∗(a∗p2)∗...∗(a∗pk)≡p1∗p2∗...∗pk(modp)∴(a*p_1)*(a*p_2)*...*(a*p_k)\equiv p_1*p_2*...*p_k(mod\ p)∴(a∗p1)∗(a∗p2)∗...∗(a∗pk)≡p1∗p2∗...∗pk(mod p)
∴aϕ(p)≡1(modp)∴a^{\phi(p)}\equiv 1(mod\ p)∴aϕ(p)≡1(mod p) 扩展欧拉定理 若a,ma,ma,m为正整数当rϕ(m)r\phi(m)rϕ(m)时有ar≡ar%ϕ(m)ϕ(m)a^r\equiv a^{r\%\phi(m)\phi(m)}ar≡ar%ϕ(m)ϕ(m) 证明
分类讨论 .如果(a,m)1(a,m)1(a,m)1则显然成立 因为由欧拉定理得aϕ(m)≡1(modm)a^{\phi(m)}\equiv1\pmod maϕ(m)≡1(modm) 若(a,m)1(a,m)1(a,m)1 引理一 如果满足 {x≡y(modm)x≡y(modn)\begin{cases}x\equiv y\ (mod\ m)\\x\equiv y\ (mod\ n)\end{cases}{x≡y (mod m)x≡y (mod n) 则有 x≡y(modlcm(n,m))x\equiv y\ (mod\ \ lcm(n,m))x≡y (mod lcm(n,m)) 证明 显然(x−y)(x-y)(x−y)既是mmm的倍数又是nnn的倍数则其必然为lcm(n,m)lcm(n,m)lcm(n,m)的倍数 引理二 如果ppp为质数ϕ(pq)≥q\phi(p^q)\ge qϕ(pq)≥q 证明
给两种证明方法
法一
以每ppp个为一个周期划分
显然(p,p−1)1,(p2,p2−1)1,...,(pq,pq−1)1(p,p-1)1,(p^2,p^2-1)1,...,(p^q,p^q-1)1(p,p−1)1,(p2,p2−1)1,...,(pq,pq−1)1
此时光考虑一部分就已经满足ϕ(pq)q\phi(p^q)qϕ(pq)q故引理显然成立 法二
ϕ(pq)pq−1∗(p−1)\phi(p^q)p^{q-1}*(p-1)ϕ(pq)pq−1∗(p−1)
根据数学归纳法
考虑q1,ϕ(p)1q1,\phi(p)1q1,ϕ(p)1显然成立
设qkqkqk时成立即pk−1∗(p−1)kp^{k-1}*(p-1)kpk−1∗(p−1)k
∵k1∵k1∵k1
∴∴∴显然pk∗(p−1)k1p^k*(p-1)k1pk∗(p−1)k1
即当qk1qk1qk1时也成立 接下来继续证明扩展欧拉定理 若mpkmp^kmpk即mmm为质数的幂时 ∵(a,m)1∵(a,m)1∵(a,m)1 ∴p∣a∴p\bigg|a∴p∣∣∣∣a 由引理二可得ϕ(pk)≥k\phi(p^k)\ge kϕ(pk)≥k即ϕ(m)≥k\phi(m)\ge kϕ(m)≥k ∴rϕ(m)≥k∴r \phi(m)\ge k∴rϕ(m)≥k ∴arx∗pry∗pϕ(m)z∗pk∴a^rx*p^ry*p^{\phi(m)}z*p^k∴arx∗pry∗pϕ(m)z∗pk从ppp的指数上抽一些下来使x→y→zx\rightarrow y\rightarrow zx→y→z 即m∣ar,m∣pϕ(m)m\bigg|a^r,m\bigg|p^{\phi(m)}m∣∣∣∣ar,m∣∣∣∣pϕ(m) ∴ar≡ar%ϕ(m)ϕ(m)≡0(modm)∴a^r\equiv a^{r\%\phi(m)\phi(m)}\equiv 0(mod\ \ m)∴ar≡ar%ϕ(m)ϕ(m)≡0(mod m) 若mp1k1p2k2...pnknmp_1^{k_1}p_2^{k_2}...p_{n}^{k_n}mp1k1p2k2...pnkn 设m1p1k1m_1p_1^{k_1}m1p1k1则ar≡ar%ϕ(m1)ϕ(m1)(modm1)a^r\equiv a^{r\%\phi(m_1)\phi(m_1)}\ \ (mod\ \ m_1)ar≡ar%ϕ(m1)ϕ(m1) (mod m1) 设m2p2k2m_2p_2^{k_2}m2p2k2则ar≡ar%ϕ(m2)ϕ(m2)(modm2)a^r\equiv a^{r\%\phi(m_2)\phi(m_2)}\ \ (mod\ \ m_2)ar≡ar%ϕ(m2)ϕ(m2) (mod m2) .................. 设mnpnknm_np_n^{k_n}mnpnkn则ar≡ar%ϕ(mn)ϕ(mn)(modmn)a^r\equiv a^{r\%\phi(m_n)\phi(m_n)}\ \ (mod\ \ m_n)ar≡ar%ϕ(mn)ϕ(mn) (mod mn) m1,m2,...,mnm_1,m_2,...,m_nm1,m2,...,mn 不同的质数的幂两两互质 ϕ(m)ϕ(m1)∗ϕ(m2)∗...∗ϕ(mn)\phi(m)\phi(m_1)*\phi(m_2)*...*\phi(m_n)ϕ(m)ϕ(m1)∗ϕ(m2)∗...∗ϕ(mn) 又根据引理一则得到 ar≡ar%ϕ(m)ϕ(m)(modm)a^r\equiv a^{r\%\phi(m)\phi(m)}\pmod mar≡ar%ϕ(m)ϕ(m)(modm)
区间逆元 如果整数a,ba,ba,b满足a∗b%p1a*b\%p1a∗b%p1则称a,ba,ba,b在模ppp的意义下互为逆元 只有(a,p)1(a,p)1(a,p)1在模ppp的意义下aaa才有逆元aaa的逆元记作a−1a^{-1}a−1 证明
若(a,p)1(a,p)1(a,p)1则令dgcd(a,p),d∣a,d∣pdgcd(a,p),d|a,d|pdgcd(a,p),d∣a,d∣p
∴d∣a%p∴d|a\%p∴d∣a%p感性理解为x倍ddd减去y倍ppp直到xyxyxy其差一定也为ddd的倍数
∴a≡(x%y)d(modp)∴a\equiv (x\%y)d\ (mod\ \ p)∴a≡(x%y)d (mod p)
∵d1∵d1∵d1
∴(x%y)d≠1∴(x\%y)d≠1∴(x%y)d1 逆元的性质若(b,p)1(b,p)1(b,p)1则a/b%pa∗b−1%pa/b\%pa*b^{-1}\%pa/b%pa∗b−1%p 有一种求区间逆元的方式时间复杂度为O(n)O(n)O(n) 设模数为m,f[n]m,f[n]m,f[n]表示nnn的逆元其中[1,n)[1,n)[1,n)的逆元已经求出则 f[n](−f[m%n]∗(m/n)%mm)%mf[n](-f[m\%n]*(m/n)\%mm)\%mf[n](−f[m%n]∗(m/n)%mm)%m 证明 公式一 f[i]−f[m−i]f[i]-f[m-i]f[i]−f[m−i] 证明
f[i]∗i≡1(modm)f[i]*i\equiv1\ \ \ (mod\ m)f[i]∗i≡1 (mod m)
f[i]∗(m−i)≡−1(modm)f[i]*(m-i)\equiv-1\ \ \ (mod\ m)f[i]∗(m−i)≡−1 (mod m)
f[m−i]∗(m−i)≡1(modm)f[m-i]*(m-i)\equiv1\ \ \ (mod\ m)f[m−i]∗(m−i)≡1 (mod m)
f[i]−f[m−i]f[i]-f[m-i]f[i]−f[m−i] 公式二 f[i]k∗f[k∗i]f[i]k*f[k*i]f[i]k∗f[k∗i] 证明
f[i∗k]∗(i∗k)≡1(modm)f[i*k]*(i*k)\equiv 1\ \ \ (mod\ m)f[i∗k]∗(i∗k)≡1 (mod m)
(f[i∗k]∗k)∗i≡1(modm)(f[i*k]*k)*i\equiv 1\ \ \ (mod\ m)(f[i∗k]∗k)∗i≡1 (mod m)
f[i]∗i≡1(modm)f[i]*i\equiv 1\ \ \ (mod\ m)f[i]∗i≡1 (mod m)
f[i∗k]∗kf[i]f[i*k]*kf[i]f[i∗k]∗kf[i] f[n]k∗f[k∗n]m/n×f[m−m%n]f[n]k*f[k*n]m/n\times f[m-m\%n]f[n]k∗f[k∗n]m/n×f[m−m%n]
f[m−m%n]−f[m%n]f[m-m\%n]-f[m\%n]f[m−m%n]−f[m%n]
f[n]m/n×(−f[m%n])f[n]m/n\times (-f[m\% n])f[n]m/n×(−f[m%n]) inv[1] 1;
for( int i 2;i n;i )inv[i] ( mod - mod / i ) * inv[mod % i] % mod;扩展欧几里得
扩展欧几里得是用来求不定方程axbycaxbycaxbyc且已知整数a,b,ca,b,ca,b,c 要求gcd(a,b)∣cgcd(a,b)|cgcd(a,b)∣c才能保证有解
算法思想递归求解
先求方程axbygcd(a,b)axbygcd(a,b)axbygcd(a,b)求出该方程的解乘上系数c/gcd(a,b)c/gcd(a,b)c/gcd(a,b)即为原方程的解 axbygcd(a,b)gcd(b,a%b)bx′(a%b)y′bx′(a−a/b∗b)y′axbygcd(a,b)gcd(b,a\%b)bx(a\%b)ybx(a-a/b*b)yaxbygcd(a,b)gcd(b,a%b)bx′(a%b)y′bx′(a−a/b∗b)y′ 将a,ba,ba,b看做变量移项合并同类项 axbybx′(a−a/b∗b)y′axbybx(a-a/b*b)yaxbybx′(a−a/b∗b)y′ axby−bx′−ay′a/b∗by′0axby-bx-aya/b*by0axby−bx′−ay′a/b∗by′0 xa−y′ayb−x′ba/b∗y′b0xa-yayb-xba/b*yb0xa−y′ayb−x′ba/b∗y′b0 (x−y′)a(y−x′a/b∗y′)b0(x-y)a(y-xa/b*y)b0(x−y′)a(y−x′a/b∗y′)b0 ∵a∗b≠0∵a*b≠0∵a∗b0 ∴x−y′0,y−x′a/b∗y′0∴x-y0,y-xa/b*y0∴x−y′0,y−x′a/b∗y′0 ∴{xy′yx′−y′∗(a/b)∴\begin{cases}xy\\yx-y*(a/b)\end{cases}∴{xy′yx′−y′∗(a/b) 只需要求出x′,y′x,yx′,y′就可以求出x,yx,yx,y
而求x′,y′x,yx′,y′可以继续递归下去
gcd(a,b)gcd(a,b)gcd(a,b)中的参数bbb最终会变为000此时gcd(a,0)agcd(a,0)agcd(a,0)a
于是有axbygcd(a,0)aaxbygcd(a,0)aaxbygcd(a,0)a可以求出x1,y0x1,y0x1,y0
这是最底层的x,yx,yx,y然后一层层返回就可以求出最原始的x,yx,yx,y了 注意exgcdexgcdexgcd求出来的x,yx,yx,y满足的方程组是axbxgcd(a,b)axbxgcd(a,b)axbxgcd(a,b)
将这一对x,yx,yx,y乘上cgcd(a,b)\frac{c}{gcd(a,b)}gcd(a,b)c才是原方程的一组解
而且这一组解只是一组特解并不一定是最小的可以通过通解公式去找到最小解xxx
axbycaxbycaxbyc a(x−k)b(yakb)ca(x-k)b(y\frac{ak}{b})ca(x−k)b(ybak)c 因为aaa缩小若干倍为了保证方程的正确性bbb就应该放大若干倍所以需满足b∣akb\bigg|akb∣∣∣∣ak ∴bgcd(a,b)∣agcd(a,b)k∴\frac{b}{gcd(a,b)}\bigg|\frac{a}{gcd(a,b)}k∴gcd(a,b)b∣∣∣∣gcd(a,b)ak ∵(bgcd(a,b),agcd(a,b))1∵(\frac{b}{gcd(a,b)},\frac{a}{gcd(a,b)})1∵(gcd(a,b)b,gcd(a,b)a)1 ∴bgcd(a,b)∣k∴\frac{b}{gcd(a,b)}|k∴gcd(a,b)b∣k 所以原方程的aaa可以无限缩小bgcd(a,b)\frac{b}{gcd(a,b)}gcd(a,b)b倍直到abgcd(a,b)a\frac{b}{gcd(a,b)}agcd(a,b)b
同理通解也可以被表示出来Xxt×bgcd(a,b),Yy−t×agcd(a,b)Xxt\times \frac{b}{gcd(a,b)},Yy-t\times \frac{a}{gcd(a,b)}Xxt×gcd(a,b)b,Yy−t×gcd(a,b)a
void exgcd( int a, int b, int d, int x, int y ) {if( ! b ) d a, x 1, y 0;else {exgcd( b, a % b, d, y, x );y - x * ( a / b );}
}//求x的最小解
x ( x * ( c / d ) % ( b / d ) ( b / d ) ) % ( b / d )中国剩余定理 求一个模线性方程组xxx {x≡a1(modr1)x≡a2(modr2)...x≡ak(modrk)\begin{cases}x\equiv a_1\ \ (mod\ \ r_1)\\x\equiv a_2\ \ (mod\ \ r_2)\\...\\x\equiv a_k\ \ (mod\ \ r_k)\end{cases}⎩⎪⎪⎪⎨⎪⎪⎪⎧x≡a1 (mod r1)x≡a2 (mod r2)...x≡ak (mod rk) 其中r1,r2,...,rkr_1,r_2,...,r_kr1,r2,...,rk互质 对于rir_iri设Ai∏j≠irjA_i\prod_{j≠i}r_jAi∏jirj
∵(r1,r2,...,rk)1∵(r_1,r_2,...,r_k)1∵(r1,r2,...,rk)1
∴(Ai,ri)1∴(A_i,r_i)1∴(Ai,ri)1
则一定存在一个整数cic_ici满足ci∗Ai%ri1c_i*A_i\% r_i1ci∗Ai%ri1
设xiai∗ci∗Aix_ia_i*c_i*A_ixiai∗ci∗Ai则xi%riaix_i\%r_ia_ixi%riai
因为AiA_iAi是除了rir_iri以外的其他rrr值的最小公倍数
所以xi%rj0(j≠i)x_i\%r_j0(j≠i)xi%rj0(ji)即xix_ixi模其他的rrr余数都为000只有模rir_iri的时候余数为aia_iai
换言之把xix_ixi加到满足其他方程j(j≠i)j(j≠i)j(ji)的解xjx_jxj上(xixj)(x_ix_j)(xixj)也一样满足方程jjj
同理如果xjx_jxj也是这么求出来的则(xixj)(x_ix_j)(xixj)也满足方程iii
那么我们对于每一个方程都按照这个方法求出来该方程的解
把这些解累加起来发现这个和仍然满足每一个方程
即x∑i1kai∗ci∗Ai%rix\sum_{i1}^ka_i*c_i*A_i\%r_ix∑i1kai∗ci∗Ai%ri
对于xxx加上所有的rrr值的最小公倍数它仍然满足所有方程
所以只要存在xxx则意味着有无穷多组解
通解为x∑i1k(ai∗ci∗Ai%ri)p∗∏i1kri,p∈Zx\sum_{i1}^k(a_i*c_i*A_i\%r_i)p*\prod_{i1}^kr_i,p∈Zxi1∑k(ai∗ci∗Ai%ri)p∗i1∏kri,p∈Z 扩展中国剩余定理 求一个模线性方程组xxx {x≡a1(modr1)x≡a2(modr2)...x≡ak(modrk)\begin{cases}x\equiv a_1\ \ (mod\ \ r_1)\\x\equiv a_2\ \ (mod\ \ r_2)\\...\\x\equiv a_k\ \ (mod\ \ r_k)\end{cases}⎩⎪⎪⎪⎨⎪⎪⎪⎧x≡a1 (mod r1)x≡a2 (mod r2)...x≡ak (mod rk) 其中r1,r2,...,rkr_1,r_2,...,r_kr1,r2,...,rk不一定互质 首先取前两个方程xk∗r1a1p∗r2a2xk*r_1a_1p*r_2a_2xk∗r1a1p∗r2a2k∗r1−p∗r2a2−a1k*r_1-p*r_2a_2-a_1k∗r1−p∗r2a2−a1
这种形如axbycaxbycaxbyc的不定方程可以用扩展欧几里得计算
当gcd(r1,r2)gcd(r_1,r_2)gcd(r1,r2)不能整除a2−a1a_2-a_1a2−a1时方程组无解
否则根据exgcdexgcdexgcd求出k0k_0k0满足k0∗r1−p∗r2a2−a1k_0*r_1-p*r_2a_2-a_1k0∗r1−p∗r2a2−a1
kkk的通解为 kk0b∗(r2/gcd(r1,r2))kk_0b*(r_2/gcd(r_1,r_2))kk0b∗(r2/gcd(r1,r2))
带入到方程组xk∗r1a1xk*r_1a_1xk∗r1a1中则有x(k0b∗(r2/gcd(r1,r2)))∗r1a1k0∗r1b∗lcm(r1,r2)a1,b∈Zx(k_0b*(r_2/gcd(r_1,r_2)))*r_1a_1k_0*r_1b*lcm(r_1,r_2)a_1,b∈Zx(k0b∗(r2/gcd(r1,r2)))∗r1a1k0∗r1b∗lcm(r1,r2)a1,b∈Z 即x≡a1(modlcm(r1,r2))x\equiv a_1\ \ (mod\ \ lcm(r_1,r_2))x≡a1 (mod lcm(r1,r2)) 这个方程相当于合并了原来的两个方程而形式上又和原来的方程一致
继续采用这个方法不断地合并方程组中的两个方程
直到最后合并为一个方程则可以得到xxx的通解
注意在这个过程中要注意求出的k0k_0k0是k∗r1−p∗r2(a2−a1)k*r_1-p*r_2(a_2-a_1)k∗r1−p∗r2(a2−a1)的解
而不是k∗r1−p∗r2gcd(r1,r2)k*r_1-p*r_2gcd(r_1,r_2)k∗r1−p∗r2gcd(r1,r2)的解前者是后者的倍数
//扩展中国剩余定理求最小整数解x的模板代码
#include cstdio
#define MAXK 10000005
#define int long long
int mod[MAXK], r[MAXK];void exgcd( int a, int b, int d, int x, int y ) {if( ! b ) d a, x 1, y 0;else {exgcd( b, a % b, d, y, x );y - x * ( a / b );}
}int Fabs( int x ) {return ( x 0 ) ? -x : x;
}signed main() {int m;while( ~ scanf( %lld, m ) ) {for( int i 1;i m;i )scanf( %lld %lld, mod[i], r[i] );int noans 0, d, x, y;for( int i 1;i m;i ) {exgcd( mod[i], mod[i 1], d, x, y );if( Fabs( r[i 1] - r[i] ) % d ) {noans 1;break;}x ( x * ( ( r[i 1] - r[i] ) / d ) % ( mod[i 1] / d ) ( mod[i 1] / d ) ) % ( mod[i 1] / d );int lcm mod[i] / d * mod[i 1];mod[i 1] lcm, r[i 1] ( x * mod[i] r[i] ) % lcm;}if( noans ) printf( -1\n );else printf( %lld\n, r[m] );
//r[m]可能等于0所以根据题目要求若要最小正整数则为mod[m]}return 0;
}终于写完了
利用以上所有知识进行证明 若ppp是质数p3p3p3则2p12p12p1和4p24p24p2至多有一个数是质数 抛开333的倍数肯定是合数任何整数都可以被改写成3k±13k±13k±1的形式
p3k1p3k1p3k1 2p16k33(k1)2p16k33(k1)2p16k33(k1)合数 4p212k66(2k1)4p212k66(2k1)4p212k66(2k1)合数p3k−1p3k-1p3k−1 2p16k−12p16k-12p16k−1未知 4p212k−22(6k−1)4p212k-22(6k-1)4p212k−22(6k−1)合数
最多就是那个未知情况为质数得证 gcd(f(n),f(m))f(gcd(n,m))gcd(f(n),f(m))f(gcd(n,m))gcd(f(n),f(m))f(gcd(n,m)) f:f:f: 斐波拉契数列 gcd(an−1,am−1)agcd(n,m)−1\gcd(a^n-1,a^m-1)a^{gcd(n,m)}-1gcd(an−1,am−1)agcd(n,m)−1
