定义

同余定理是数论四大基本定理之一，在acm中常常用到，他的表达形式为a≡b (mod m)。这代表着a与b关于m同余，读作a同余于b模m

应用

同余定理常常配合其他数论算法使用，单独考察同余的地方不多，一般是对1e9+ 7求余以确保答案在32位整数范围内

练习题

https://v4t.jk1507.cn/problem.php?pid=3899

#include <stdio.h>
#include <string.h>

#define N 11000
#define MOD 1000000007

typedef long long LL;

LL qpow(LL a, LL b) {
    if (b == 0) return 1;
    if (b == 1) return a % MOD;

    LL ans = qpow(a, b / 2);
    ans = ans * ans % MOD;
    if (b & 1) ans = ans * a % MOD;
    return ans % MOD;
}

int main() {
    LL n, m;
    while (scanf("%lld%lld",&n, &m) == 2) {
        LL sum = 0;
        for (LL i = 1; i <= n; ++i) {
            sum = (sum + qpow(i, m)) % MOD;
        }
        printf("%lld\n",sum % MOD);
    }
    return 0;
}