在车人的要求下，玉帛拿一下午讲了生成函数 这个大坑不知道要填多久 前置知识：求导（真够让人头大） 这是讲解：懒得写了，全英文但勉强能看 好了看例题： 食物 - BZOJ by HydroOJ - P3028 如果看了上面的资料，那这就十分板了呀 f1=11−x2f2=1+xf3=1+x+x2f4=x1−x2f5=11−x4f6=1+x+x2+x3f7=1+xf8=11−x3⟷11−x2(1+x)(1+x+x2)x1−x211−x4(1+x+x2+x3)(1+x)11−x3=1(1+x)(1−x)(1+x)(1+x+x2)x(1+x)(1−x)x(1+x2)

莫比乌斯反演 一句话总结：题面极其简洁并且大多能一眼出算法，代码短但是式子又臭又长。 前置知识：数论分块：数论全家桶 - lfyszy（别问为啥没有狄利克雷卷积) 莫比乌斯函数 μ\muμ 为莫比乌斯函数，定义为： μ(n)={1n=10n含有平方因子(−1)kk为n的本质不同质因子个数\mu(n)= \begin{cases} 1&n=1\\ 0&n\text{ 含有平方因子}\\ (-1)^k&k\text{ 为 }n\text{ 的本质不同质因子个数}\\ \end{cases}μ(n)=⎩⎨⎧​10(−1)k​n=1n含有平方因子k为n的本质不同质因子个数​ 同时莫比乌斯函数有

闲话 我谔谔，第一稿写了一大部分没有保存。 质数 & 约数 质数判定 试除法 没啥好说，会的都会，复杂度 O(n)O(\sqrt{n})O(n​) 1 2 3 4 5 6 7 bool isprime(int x) { if(x == 1) return false; for(int i = 2; i <= n / i; i ++) if(x % i == 0) return false return true; } Fermat 素性检验 通过反着使用费马小定理，多次换底增加正确性。 但是可以被卡迈尔数完美卡掉。 Miller Rabi