最大公约数、同余原理

求最大公约数

欧几里得算法（辗转相除法）

//若较大的数字为a，则O((loga)^3)
public static long gcd(long a, long b){
    return b == 0 ? a : gcd(b, a % b);;
}

• 证明：gcd(a, b) = gcd(b, a % b)
• 设a % b = r,即gcd(a, b) = gcd(b, r)
• 可得：a = b * q + r(q为整数)，r = a - b * q(q为整数)
• 设u为a和b的公因子，则有a=su,b=tu
• ∴r=su-tuq=(s-tq)*u
• 说明u也是r的因子
• 同理设v为b和r的公因子，可推得v是a的因子
• ∴a和b的全体公因子集合=b和r的全体公因子集合
• ∴gcd(a, b) = gcd(b, r)

最小公倍数

public static long lcm(long a, long b){
    return (long) a / gcd(a, b) * b;
}

例题：
    一个数能被a或b整除，那么它是神奇的，给定三个整数n,a,b,返回第n个神奇的数字，因为答案可能很大，所以返回答案对10……9+7取模后的值
二分答案法+容斥原理

public static int nthMagucalNumver(int n, int a. int b){
  long lcm  = lcm(a, b);
  long ans = 0;
  for(long l  = 0, r = (long) n * Math.min(a, b),m = 0; l <= r;){
    m = (l + r) / 2;//1~m上有多少个，小于n于往右，大于往左
    if(m / a + m / b - m / lcm >=n){//a的数+b的数-重复的数
      ans = m;
      r = m - 1;
    }
    else{
      l = m + 1;
    }
  }
  return (int)(ans % 1000000007);
}

Stein算法

同余原理

对中间量进行取与，使得每个计算的时间可控

k位整数 +-运算O(k)，认为 O(32),O(64)为O(1)
*/为O(k^2)
超出字位再进行运算时，复杂度会增加

加法同余原理：过程量取模相乘=最终量取模，防止过程量溢出
乘法同余原理：过程量取模相乘=最终量取模，防止过程量溢出
乘法同余原理：(a-b)%m=(a%m-b%m+m)%m,a-b转为两个余数相减同时可能为负数

真实值最后取模

数字字位溢出