数论

发表于 | 更新于: |

a,b的最小公倍数和最大公因数

  • a*b=gcd(a,b)xlcm(a,b)

    素数筛

    埃氏筛

  • 几种优化
  1. 分块筛法，将要筛选的区间进行分块，对每个块进行处理，这样就不用一直保存整个范围的vis数组，利于cpu更好地处理缓存.
  2. 减少内存的占用,采用位级压缩，但这种压缩方法会使这些位的操作复杂化。任何位上的读写操作都需要多次算术运算。这是一种以降低内存占用，从而降低执行效率的方法
  3. 只筛选奇数.

    Euler筛

    扩展欧几里得定理

  • ax+by=gcd(a,b) 归纳法证明？
  • 二进制求最大公因数(校赛)
  • 倒水问题(贝祖定理)

    比赛数论例题

    洛谷100月赛 Q1

  • 思路：如果一个数的因子有K个,那么使得这个数最小的方案是2^k,也就是全是2.首先想到两个特殊值4,9。
  • 先说4，可以因式分解为2x2.再说9，可以分解为3*3.
  • 归纳出，如果一个数的质因子大于5小于9，那么一定存在一个数小于他，并且因子大于他，因为大于5小于9的这个因子可以写成2x2.举个例子，14=2x7,一定存在一个数,2x2x2=8.
  • 如果一个数的质因子大于等于9，那么一定存在一个数小于他，并且因子数大于他，因为这个质因子肯定没有2x2x2这个因子数多。举个例子，18这个数可以写成3x3x2,3x3可以优化成2x2x2，那么这个数就是2x2x2x2=16.

    CodeForce 767 Q2

  • [l,r]的连续整型数组，最多操作k次，每次将数组中两个数字相乘，问是否最终存在一个数组，整个数组的gcd大于1.
  • 思路：可以假设最终的数组的gcd是多少。经过找规律可以发现，如果最终的gcd是x，最终长度为N的数组剩下的数字的个数为N/x(素数筛的原理)，可以发现当最终数组的x=2时，可以使得数组剩下的数更多，需要的k更小。

    ACM校赛Q1

  • 思路：找素数的规律(素数的定义)

    AcM校赛QL

  • 思路：根据题设条件变形，再根据a/gcd(a,b)+b/gcd(a,b)=2k，两个数为奇数，而且因子2的个数相同(否则不可能为奇数)。

    一道有意思的欧拉筛题 牛客KY7

  • 尽管题设条件给的是[1,1e9],但是并不用将欧拉筛的取值范围设置为1e9,因为题设并没有要求我们找出1e9以内的所有质数，只用找出质因子的个数即可。
  • 那为什么是1e6呢？因为就算一个数存在两个质数1e6*1e6,已经超过了1e9的范围。例如，夸张一点假设，如果将primes[]数组大小改为1e1,此时就不成立了，存在一个数字有两个因子17x17=289，这样就筛不出正确的因子个数了。
  • 测试用例举例：799043235，分解因式3x5x5x29x1259x1459.如果此时将N设置为1e3,很明显会出错.

欧拉函数

  • 实现过程：在分解质因数的过程中求出欧拉函数

递推

卡特兰数

  • 通过两种思路得到的递推方式得到一个更为简洁的递推公式：f(n+1)=(4n-6)/f(n).

    组合数与杨辉三角

  • 根据杨辉三角的性质得出递推式: C[i][j]=C[i-1][j]+C[i-1][j-1]
  • 凡是需要提前求出C(n,i)值，都可以利用杨辉三角

    UVa12034

  • 两种思路：第一种先确定第一名，依次第二名…第n名。
  • 第二种思路，dp[i][j]:i匹马，j个名次的所有方案=(dp[i-1][j-1]+dp[i-1][j])*j.也有点类似杨辉三角.i-1匹马形成j-1个名词，再来一匹马，与之前的马混用名次，j种方案。其次，i-1匹马形成j-1个名次，再来一匹马，新形成一个名次，也是j种方案。