约数之和

#include <bits/stdc++.h>
using namespace std;
const int mod=9901;
int ans=1;
int quick(int a,int b) {
    int res = 1;
    a=a%mod;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int calc(int p,int k) {
    if (k == 0) {
        return 1;
    }
    if (k % 2 == 0) {
        return (p % mod * calc(p, k - 1) + 1) % mod;
    }
    return (1 + quick(p, k / 2 + 1)) * calc(p, k / 2) % mod;
}
int main() {
    int A, B;
    scanf("%d%d", &A, &B);
    if (!A) {
        printf("0\n");
        return 0;
    }
    for (int i = 2; i <= A; i++) {
        int k = 0;
        while (A % i == 0) {
            A = A / i;
            k++;
        }
        if (k) {
            ans = ans * calc(i, k * B)%mod;
        }
    }
    printf("%d\n",ans);
}

处理阶乘和阶乘的逆元

void init(int n)
{
    f[0]=1;
    for (int i=1; i<=n; i++)
    {
        f[i]=f[i-1]*i%mod;
    }
    inv[n]=quick(f[n],mod-2);
    for(int i=n-1; i>=0; i--)
    {
        inv[i]=inv[i+1]*(i+1)%mod;
    }
}

线性求逆元

void get_inv(int n){
    inv[1]=1;
    for (int i=2;i<=n;i++){
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    }
}　　

Lucas

int Lucas(int n,int m){
    if (!m){
        return 1;
    }
    return (C(n%p,m%p)*Lucas(n/p.m/p)%p);
}

中国剩余定理

模p余a,p两两互质
void exgcd(ll a,ll b,ll &d,ll &x.ll &y){
    if (!b){
        d=a;
        x=1;
        y=0;
    }
    exgcd(b,a%b,d,y,x);
    y-=a/b*x;
}
ll inv(ll a,ll p){
    ll d,x,y;
    exgcd(a,b,d,x,y);
    return d==1?(x%p+p)%p:-1;
}
ll CRT(){
    ll ret=0,lcm=1;
    for (int i=1;i<=n;i++){
        lcm=lcm*p[i];
    }
    for (int i=1;i<=n;i++){
        ll x=lcm/p[i];
        ll k=inv(x,p[i]);
        ret=(ret+a[i]*x*k)%lcm;
    }
    return ret;
}

模p余a,p两两不互质
void exgcd(ll a,ll b,ll &d,ll &x.ll &y){
    if (!b){
        d=a;
        x=1;
        y=0;
    }
    exgcd(b,a%b,d,y,x);
    y-=a/b*x;
}
ll CRT(){
    ll P=p[1],A=a[1],t;
    for (int i=2;i<=n;i++){
        ll d,x,y;
        exgcd(P,p[i],d,x,y);
        if ((a[i]-A)%d) return -1;
        x*=(a[i]-A)/d;
        t=p[i]/d;
        x=(x%t+t)%t;
        A=P*x+A;
        P=P/d*p[i];
        A%=P;
    }
    A=(A%P+P)%P;
    return A;
}