数论全集

欧几里得算法、拓展欧几里得算法

欧几里得算法：$gcd(a,b)=gcd(b,a\% b)$

int gcd(int a,int b) {
  if (b==0) return a;
  return gcd(b,a%b);
}

快速欧几里得算法（更相减损术）：$gcd(a,b)=gcd(b,a-b)$

#define ctz __builtin_ctzll
LL gcd(LL a,LL b) {
  if(!a) return b;
  if(!b) return a;
  int t=ctz(a|b);
  a>>=ctz(a);
  do {
    b>>=ctz(b) ;
    if(a>b) swap(a,b);
    b-=a;
  } while(b);
  return a<<t;
}

拓展欧几里得算法：解不定方程$ax+by=gcd(a,b)$

算$gcd(a,b)$时，
有$ax+by=gcd(a,b)$ $(1)$
算$gcd(b,a\%b)$时，
有$bx'+(a\%b)y'=gcd(b,a\%b)$ $(2)$
设$lfloor frac{a}{b} floor=k$，有$a \% b = a-kb$
带入$(2)$，有$ay'+b(x'-ky')=gcd(a,b)$，
因为对于任意的$a,b$恒成立，所以有$
left{egin{matrix}
{y=x’-ky’} hfill
\ {x=y’} hfill
end{matrix} ight.
$
先求出$gcd$，每次求出当前的$x',y'$，然后更新上一步的。

int exgcd(int a,int b,int& x,int& y){
  int ans;
  if (b==0) {
    x=1; y=0;
    return a;
  }
  ans=exgcd(b,a%b,x,y);
  int tx=x;
  x=y; y=tx-a/b*y;
  return ans;
}

整除与互质的性质

互质

当$gcd(a,b)=1$时，称a、b互质（素）
性质：

整除

设$a,b$为整数，$a≠0$，若有一整数$q$，使得$b=aq$，则称$a$是$b$的因数，$b$为$a$的倍数；并称$a$整除$b$，记为$a|b$；若$a$不能整除$b$，则记为$a|b$。
性质：

1、若$c|b$且$b|a$，则$c|a$
2、若$c|a$且$d|b$，则$cd|ab$
3、若$c|a$且$c|b$，则$c|(ka+nb)$。
4、若$ma|mb$，则$a|b$
5、若$a>0$，$b>0$，且$b|a$，则$b le a$
6、若$n$为正整数，则$(a-b)|(a^n-b^n)$；若$n$为奇数，则$(a+b)|(a^n+b^n)$；若$n$为偶数，则$(a+b)|(a^n-b^n)$

同余

设$m$是正整数，若$m|(a-b)$，称$a$和$b$对模$m$同余，记作$a≡b pmod m$
性质：

1、$a≡a pmod m$
2、若$a≡b pmod m$，则$b≡a pmod m$
3、若$a≡b pmod m$，$b≡c pmod m$，则$a≡c pmod m$
4、若$a≡b pmod m$，$c≡d pmod m$，则$a±c≡b±d pmod m$，$ac≡bd pmod m$
5、若$(m,n)=1$，$a≡b pmod m$，$a≡b pmod n$，则$a≡b pmod {mn}$
6、若$a≡b pmod m$，$a^n≡b^n pmod m$
7、若$n|m$，$a≡b pmod m$，则$a≡b pmod n$
8、若$ac≡bc pmod m$，$(c,m)=d$，则$a≡b pmod {m/d}$

整数分块

引理：对于$lfloor frac{n}{i} floor$最多只有$2sqrt{n}$种取值。

当$i le sqrt{n}$时，每个$i$一种，最多只有$sqrt{n}$种。
当$i > sqrt{n}$时，$lfloor frac{n}{i} floor < sqrt{n}$，每个整的取值一种，最多只有$sqrt{n}$种。

找出这$2sqrt{n}$种取值所代表的区间。

设目前区间的左端点为$l$，我们只需找出$r$是多少即可。
有$lfloor frac{n}{l} floor = lfloor frac{n}{r} floor$。
设$lfloor frac{n}{l} floor = k$，即求$kr le n$时，最大的$r$。
由“除法的定义”得$r=n/k$。

当对应单变量时：

for (ri l=1,r;l<=n;l=r+1) r=n/(n/l);

注意：不可能$r$在一次循环前小于$n$，但是在循环后大于$n$的情况，因为$n/l$最小为$1$，所以不用和$n$取$min$。

当对应双变量时（多个$2$的常数）

for(ri l=1,r;l<=min(n,m);l=r+1) r=min(n/(n/l),m/(m/l));

欧拉定理

若$a$，$p$互质，有

$$a^{varphi(p)} equiv 1 pmod{p}$$

当$a$，$p$不互质时，有

$$a^{x} equiv a^{x\% varphi(p)+varphi(p)} pmod{p}$$

中国剩余定理

若$p_i$两两互质，求方程组$
left{egin{matrix}
x equiv a_1 pmod{p_1}hfill
\ x equiv a_2 pmod{p_2}hfill
\ ...
\ x equiv a_m pmod{p_m}hfill
end{matrix} ight.
$的一个通解。

令$P=prod_{i=1}^{m}{p_i}$
$P_i=P / p_i$
$t_i=P_i^{-1} \% p_i$

有

$$x=sum_{i=1}^{n}{a_i P_i t_i}$$