Author: lllyouo
Date: 20250702
tag: 同余、快速幂
link: https://www.luogu.com.cn/problem/P4942

问题描述

link

分析

一个数字除以 $9$ 的余数等于它的各位数字之和除以 $9$ 的余数。

又因为每两位数字数字只差为 $1$ 由等差数列求和可知 $s=\frac{(l+r)\ast (r-l+1)}{2}$

避免除法，则求 $2$ 的逆元即可。

$2\ast 5\equiv 1(\mathrm{mod}9)$

$2$ 的逆元为 $5$，所以 $s\times 5mod9$ 即可。

当然，$23$ 也是 $2$ 的逆元。所以 $s\times 23mod9$ 也是正确答案。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T; cin >> T;
    while (T--) {
        long long l, r; cin >> l >> r;
        long long ans = (l + r) % 9 * ((r - l + 1) % 9) * 5 % 9;
        cout << ans << endl;
    }

    return 0;
}