Divisor and Gcd
1、算术基本定理：n的质因数分解唯一
一些常见结论：
1.素数无限
2.\(\lim_{n\rightarrow+\infty}n\prod\dfrac{n}{\frac{n}{\ln{n}}}\)(Π(n)表示<=n素数的个数)
————即n以下素数个数大约是 \(\frac{n}{\ln(n)}\)级别的
3.\(Pn = O(nlogn)\)级别的 (Pn表示素数)
4.\(\prod_{i = 1}^{n}\dfrac{1}{i} = O(logn)\)
5.\(\prod_{i = 1}^{n}\dfrac{1}{p} = O(loglogn)\)
2.整除的常见性质:
a|b ：b能被a整除
1.若\(a|b，a|c，\)则\(a|(b±c)\)。
证明：
\(b = q1*a,c = q2*a\)
$ b±c = q1a±q2a = (q1±q2)*a;$
$ ∴a|(b±c)\(
2.\)a|c,b|c,(a,b) = 1(互质) ==> ab|c\(
3.\)a|bc,(a,b) = 1 ==> a|c\(
4.\)p|ab ==> p|a或p|b$
3.公约数和公倍数
\(a = p1^{a1}*p2^{a2}...pk^{ak}\)
\(b = p1^{b1}*p2^{b2}...pk^{bk}\)
\(d = p1^{d1}*p2^{d2}...pk^{dk}\)
\(d|a ==> d1<=a1,d2<=a2..dk<=ak\)
\(d|b ==> d1<=b1,d2<=b2..dk<=bk\)
\(di<=min(ai,bi)\)
\((a,b) = Πpi^{(min(ai,bi))}\)
\([a,b] = Πpi^{(max(ai,bi))}\)
\(∴(a,b)[a,b] = a*b\)
▲竞赛中遇到能被xx整除的数的特征：
·能被2整除的数：个位上为2的倍数
·能被4整除的数：个位和十位所组成的两位数能被4整除
·能被8整除的数：百位、个位、十位所组成的三位数能被8整除（注意顺序）
·能被5整除的数：个位上为5的倍数
·能被25整除的数：十位和个位所组成的两位数能被25整除
·能被125整除的数：百位、十位、个位所组成的数能被125整除
·能被3整除的数：各个数位上的数字和能被3整除
·能被9整除的数：各个数位上的数字和能被9整除
·能被11整除的数：奇数位（从左往右数）上的数字和与偶数位上的数字和的差的绝对值能被11整除
·能被7整除的数：把个位数字截去，从余下的数中，减去个位数的2倍，如果差是7的倍数，则原数能被7整除，如果不好判断就递归处理
·能被13整除的数：把个位数字截去，从余下的数中，加上个位数的4倍，如果和是13的倍数，则原数能被13整除
·能被17整除的数：把个位数字截去，从余下的数中，加上个位数的5倍，如果和是17的倍数，则原数能被17整除，或把后三位截去，剩下的数与3倍后三位差的绝对值如果能被17整除，则原数能被17整除
·能被19整除的数：把个位数字截去，从余下的数中，加上个位数的2倍，如果和是19的倍数，则原数能被19整除，或把后三位截去，剩下的数与7倍后三位的差的绝对值如果能被19整除，则原数能被19整除
4.求公约数
1.欧几里得算法
d = a[1];
for(i = 2;i<=n;i++)
d = gcd(d,a[i]);
时间复杂度O(n+log(max ai))
2.另一种公约数的算法
·如果a,b都是奇数,那么\((a,b) = (a-b,b)\)
·如果a是偶数,b是奇数,那么\((a,b) = (a/2,b)\)
·如果a,b都是偶数,那么\((a,b) = (a/2,b/2)\)
5. 裴蜀定理(Bézout’s lemma)
是一个关于最大公约数的定理
其内容是：设a,b是不全为零的整数，则存在整数x,y , 使得$ax+by=gcd(a,b)
(a,b)|d <==> ax+by = d $存在整数解
6. 扩展欧几里得
扩展欧几里得算法实际上就是对于\(ax+by=gcd(a,b)\)，一定有一组整数解x，y使其成立
\(a \bmod b = a-(a/b)*b\)
由归纳假设存在\(u',v'\)使得\(u'b+v'(a \bmod b) = d\)
即\(u'b + v'(a-(a/b)*b) = d\)
\(v'a + (u'-(a/b)v') = d\)
于是就得到了\((a,b)\)的解
\(eg.\)
\(ax+by = 1\)
\((b*(a/b)+a mod b)x+by = 1;\)
商 余数
$b(a/bx+y)+(a mod b)x = 1; $
$ x'$ $ y'$
系数由\((a,b)->(b,a mod b)\)
\(①100x + 87y = 1;\)
\(②87(x+y) + 13x = 1; ———————x = -20,y = 23\)
$ x3 $ $ y3$
\(③13*(6x2+y2)+9x2 = 1;—————— x2 = 3,y2 = -20\)
$ x3 $ \(y3\)
\(④13x3 + 9y3 = 1;\)
\((9+4)x3 + 9y3 = 1;\)
\(9(x3+y3)+4x3 = 1; ————————— x3 = -2,y3 = 3\)
\(x4\) \(y4\)
\(⑤(4*2+1)x4+4y4 = 1;\)
$ 4(2x4+y4)+x4 = 1;$
设\(2x4+y4 = 0,x4 = 1\)可以找到一组解
那$x4 = 1,y4 = -2 $ ——————————————————再返回去找解
知道了特解之后，我们可以通过他求出方程的所有解
\(x = x0+k*b/d\)
\(y = y0-k*a/d\)
exgcd代码演示
//输出ax−by=gcd(a,b)的最小非负整数解(x,y)
#include<bits/stdc++.h>
using namespace std;
//为了在计算最大公约数gcd(a,b)的同时,找到x,y,使得ax + by = d
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x = 1;
y = 0;
return a;
}
/*
int xx,yy;
int d = exgcd(b,a%b,xx,yy);
x = yy,yy = xx-(a/b)*yy;
*/
/*
int d = exgcd(b,a%b,x,y);
int k = y;
y = x-(a/b)*y;
x = k;
*/
int d = exgcd(b,a%b,y,x);
y -= (a/b)*x;
return d;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int a,b,x,y;
cin>>a>>b;
int d = exgcd(a,b,x,y);
// cout<<"gcd = "<<d<<endl;
// cout<<"x = "<<x<<" y = "<<y<<endl;
//对于ax+by = d特解是x ,y
//通解就是x1 = x + b/(a,b)*t,y1 = y - a/(a,b)*t
//我们求的是ax + by = d;
//要求ax-by = d
//ax - b(-y) = d
y = -y;
//求最小正整数解，我们用exgcd求出的是最小整数解，有可能是负数的
while(x<0||y<0)x+=b/d,y+=a/d;
while(x>=b/d&&y>=a/d)x-=b/d,y-=a/d;
cout<<x<<" "<<y<<endl;
}
return 0;
}