欧拉定理和费马小定理

这个定理是我做codeforces题目上了解到的，这题目可以分解成为两个问题：

  1. 什么样的a1,a2,…an满足modular stability.
  2. 如何计算这些排列组合的个数.

第一个问题答案是：存在ai可以被a1…an整除。也就是说如果我们遍历d=ai的话，那么a1..an只能从(n/d)里面选择。 因为我们已经确定了最小值d, 那么相当于从n/d-1里面选择k-1个元素，也就是C(n/d-1, k-1).

第二个问题是如何计算C(n/d-1, k-1). 如果只是计算一次的话，那么时间复杂度是O(n/d * k). 解法可以看 这里. 如果考虑遍历的话那么就是nk(1+1/2+..1/(n/k)). 不过即便d=1的话，那么操作时间也是不可接受的。

其实C(n,k)可以写成n!/(k! * (n-k)!). 这里的难点是如何计算 (a/b) % MOD. 如果可以变成 (a%MOD * x) % MOD，其中 x=1/b(x是b对MOD取模的逆元). 这里就引出了费马小定理和欧拉定理了，欧拉定理是费马小定理的延伸。

费马小定理是, 如果p是质数的话，那么a^(p-1) = 1(%p). 所以x应该就是b^(p-2). 而欧拉定理则不限定p必须是质数。 欧拉定理里面有个phi(n)(toitent), 表示1<=k<=n有多少k和n是互质的。如果n是质数的话，那么phi(n)=n-1.

使用费马小定理的好处就是，我们可以预先计算出n! % MOD，至于b^(MOD-2)可以在O(lg MOD)时间内完成，基本上可以认为是个常数。 所以整体的时间复杂度就是O(lgMOD * n). 

MOD = 998244353


def pow(a, x):
    ans = 1
    while x > 0:
        if x % 2 == 1:
            ans = (ans * a) % MOD
        a = (a * a) % MOD
        x = x // 2
    return ans


def run(n, k):
    fac = [1] * (n + 1)
    for i in range(1, n + 1):
        fac[i] = (fac[i - 1] * i) % MOD

    ans = 0
    for a0 in range(1, n + 1):
        nn = n // a0 - 1
        if (nn - k + 1) < 0: break
        a = fac[nn]
        b = fac[k - 1]
        c = fac[nn - k + 1]
        d = (b * c) % MOD
        e = pow(d, MOD - 2)
        f = (a * e) % MOD
        ans = (ans + f) % MOD

    return ans