1 整除

  3|6    3整除6    6被3整除

2 模运算     

  0<=余数<除数

  (a +-* b) %m=(a%m +-* b%m) %m

  为防止余数为负

  (a - b) %m=(a%m - b%m + m) %m

  常用取模限制结果范围，这时可以在过程中每次取模

3 快速幂     

  原理：分治   aⁿ=(a^n/2)²=(a^n/4)⁴=...

  不断递归为更小的幂次的平方

  时间复杂度由 O(n) 降为 O(logn)

1 long long fastpow(long long a,int n)
2 {
3     if(n==1)return a;                
4     long long t=fastpow(a,n/2);      
5     if(n%2==1)return t*t*a;          
6     else return t*t;
7 }

   一个更好的非递归版本

　a*a=a²  a²*a²=a⁴  a⁴*a⁴=a⁸...可以更快得到较高幂次

  借助位运算 a¹¹=a^{1*2^3 + 0*2^2 + 1*2^1 + 1*2^0}

  其实就是查看次数的二进制的每一位是1还是0，是1就乘上对应的数

 1 long long fastpow(long long a,int n)
 2 {
 3     long long ans=1;         
 4     while(n)                
 5     {
 6         if(n&1)ans*=a;
 7         a*=a;
 8         n>>=1;
 9     }
10     return ans;
11 }

4  gcd最大公因数 lcm最小公倍数  

  辗转相除法  gcd(a,b)=gcd(b,a%b)   O(logn)  欧几里得算法

  意为如果a为n的几倍，b为n的几倍，a除b剩下的也是n的几倍

  更相减损术  gcd(a,b)=gcd(b,a-b)   O(logn)

  意为如果a为n的几倍，b为n的几倍，a-b一定为n的几倍

  同理 gcd(a,b,c)=gcd(a,b-a,c-a)

  lcm(a,b)gcd(a,b) = ab

  gcd(a,b,c)=gcd(gcd(a,b),c)=gcd(a,gcd(b,c))

  可随意放括号(可重复贡献) lcm也是

  gcd(a,0)=a  gcd(a,b)=gcd(a,-b)

1 int gcd(int a,int b)
2 {
3     return b==0?a:gcd(b,a%b);//辗转相除法
4 }

  思考题               

  有理数a b  求最小正整数k  使[ka,kb]内有整数

  我的思路：for(k=1;b*k-floor(a*k)<1;k++);

  (会爆 正解:递归 如果减完b<1求(1/b,1/a)的子问题 没明白为什么 求助)

5  裴pei蜀定理(贝组定理)       

  ax+by=gcd(a,b) (a b不全为0的整数) x y必有整数解

  证明：两边除以gcd(a,b)得k₁x+k₂y=1

  a/gcd(a,b) b/gcd(a,b)互质

  gcd(k₁,k₂)|m (1|1) x y有整数解

  应用：ax+by=m有没有解？如果m是gcd(a,b)的几倍 则有解

  如果ax+by=1有解 则a,b互质    

6 扩展欧几里得算法 

  ax+by=c a b c为整数且a b都不为0 设有整数解x=x₀ y=y₀ 

  x=x₀-t*b/gcd(a,b) y=y₀+t*a/gcd(a,b)为一切整数解 t是整数   

  证明：a*x+b*y=gcd(a,b) -> b*x₁+(a%b)*y₁=gcd(a,b)

     代入 a%b=a-(a/b)*b  a*y₁+b*(x_1-a/b*y₁)=gcd(a,b)

  x=y₁  y=x_1-a/b*y₁

1 int exgcd(int a,int b,int &x,int &y)
2 {
3     if(b==0){x=1;y=0;return a;}
4     int d=exgcd(b,a%b,x,y);
5     int t=x;x=y;y=t-a/b*y;
6     return d;
7 }

7 同余

   a三b(mod m) a和b对m同余 = a-b=km

   a-b=km ->ka-kb=k₁m

          ->(b+km,m)=(b,m)

          ->a/与m互质的数 b/与m互质的数 对m仍然同余

  一次同余式ax三b(mod m)(a%m!=0)

  ax-b=ym->ax-my=b

  有解=(系数1,系数2)|右边的常数=(a,m)|b

  ax%m=1(a m互质)x=a'

  (a/b)%m=((a/b)%m * bb'%m)%m=ab'%m

  必有解x=b/a=ba' y=0

  逆元的求法 1.扩展欧几里得解方程 2.费马小定理

8 费马小定理

  a^p和a对于素数p同余

  证明：{1,2,3,...,p-1}对于p互不同余

  a的因子中没有p {a,2a,3a,...,(p-1)a}对于p互不同余

  它们的余数集合{1,2,3,...,p-1}相同

  它们的元素乘积(p-1)!三(p-1)!a^p-1(mod p)

  左右除以(p-1)!(p和(p-1)!互质)

  a^p-1三1(mod p) a^p三a(mod p)

  a^p-2三a'(mod p) a'=a^p-2+kp 常用a^p-2快速幂求解

9 唯一分解定理

  标准分解式a=p1^a1p2^a2...p_k^ak a_i>0 a>1

  (a,b)=p₁^min(a1,b1)p₂^min(a2,b2)...p_k^min(ak,bk)

  [a,b]=p₁^max(a1,b1)p₂^max(a2,b2)...p_k^max(ak,bk)

 1 int fac[maxn],power[maxn];
 2 void getprimefactor(int n)
 3 {
 4     for(int i=2;i<=n;i++)
 5     {
 6         while(n%i==0)
 7         {
 8             n/=i;           //除去找到的因子 保证找到的总是质数
 9             fac[++cnt]=i;   //记录
10             power[cnt]++;
11         } 
12     }
13 }

 1 void getprimefactor(int n)
 2 {
 3     for(int i=1;i<=N&&pri[i]*pri[i]<=n;i++)
 4     {
 5         while(n%pri[i]==0)              //只在素数中找
 6         {
 7             n/=pri[i];
 8             fac[++cnt]=i;
 9             power[cnt]++;
10         }
11     }
12     if(n>1)fac[++cnt]=n,power[cnt]=1;//n是个素数
13 }

10 素数筛

  埃式筛法 仍然有重复 2和3都筛24 O(nloglogn)

  从素数*素数开始标记素数*(素数+1)、素数*(素数+2)...为合数

 1 int getprime(int n)
 2 {
 3     for(int i=2;i<=n;i++)isprime[i]=1;//默认是素数
 4     isprime[0]=isprime[1]=0;        //0、1不是素数
 5     for(int i=2;i<=n;i++)   
 6     {
 7         if(isprime[i]) 
 8         {
 9             prime[++cnt]=i;               //记录
10             for(int j=i*i;j<=n;j+=i)isprime[j]=0;//尚未遍历的素数倍数
11         }
12     }
13 }

  欧拉筛 无重复 O(n) 2->4  3->6-9  4->8  5->10-15-25  6->12

  每一个合数被其最小质因子筛掉

 1 int getprime(int n)
 2 {
 3     for(int i=2;i<=n;i++)
 4     {
 5         if(!isprime[i])pri[++cnt]=i;
 6         for(int j=1;j<=cnt;j++)
 7         {
 8             if(i*pri[j]>n)break;
 9             isprime[i*pri[j]]=1;
10             if(i%pri[j]==0)break;
11         }
12     }
13 }

11 欧拉函数

  φ(n) 和n互质的<=n的数的个数

  φ(1)=1 质数pφ(p)=p-1

  积性函数 如果(a,b)=1 φ(a*b)=φ(a)*φ(b)

  φ(n)=nΠ_i=1^s (1-1/p_i)

  n前和n互质的数的个数=n*(1-1/质因数₁)(1-1/质因数₂)...

  φ(n)=Π_i=1^sφ(p_i^k_i)(唯一分解定理)

       =Π_i=1^s(p_i-1)p_i^k_i-1

       =Π_i=1^sp_i^k