1 条题解
-
0
给定 ,,求 $\overline l \quad \overline{(l + 1)} \quad \overline{(l + 2)}\quad \cdots \quad \overline{(r - 1)} \quad \overline{(r)} \quad \% \quad9$ 的值。
看到 ,容易想到该性质:
$$X \mod 9 = (x_1 \mod 9 + x_2 \mod 9 + \cdots + x_n \mod 9) \mod 9 $$其中, 表示 的最高位, 表示 的最低位(即个位)。
通俗地说,就是:一个数除以 的余数等于它各个位上的数除以 的余数之和再除以 的余数。
证明很简单:
首先, 可以写成如下形式:$x_1 \times 10^n + x_2 \times 10^{n - 1} + \cdots + x_{n - 1} \times 10^1 + x_n \times 10^0$。
考虑对 进行拆分,显然,对于任何一个 ,有 $10^i = (\sum\limits_{j = 0}^{i - 1} 9 \times 10^{j}) + 1$。
那么 就可以写为:
$$\left[(x_1 \times \sum\limits_{j = 0}^{n - 1} 9 \times 10^{j}) + x_1 \times 1 \right] + \left[(x_2 \times \sum\limits_{j = 0}^{n - 2} 9 \times 10^{j}) + x_2 \times 1 \right] + \cdots + \left[(x_{n - 1} \times \sum\limits_{j = 0}^{0} 9 \times 10^{j}) + x_{n - 1} \times 1 \right] + x_n $$很显然,对于任何的 ,结果一定等于 。
于是 就等于 ,也就是 $(x_1 \mod 9 + x_2 \mod 9 + \cdots + x_n \mod 9) \mod 9$。
那么这题就可以转化为求 的值,用等差数列求和公式可以做到每个问题 解决。
需要注意的是,在使用等差数列求和公式的时候,由于 的分母太大,即使用 也会溢出,所以可以判断 和 的奇偶性,把偶数的那个先除以 ,模 ,再把另一个数模 。最后两数相乘,模 。
#include <bits/stdc++.h> using namespace std; #define int long long int q; signed main() { cin >> q; while (q--) { int l, r; cin >> l >> r; int a = l + r, b = r - l + 1; (a % 2 == 0) ? (a /= 2) : (b /= 2); cout << ((a % 9) * (b % 9)) % 9 << endl; } return 0; }
- 1
信息
- ID
- 3871
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 2
- 标签
- 递交数
- 5
- 已通过
- 2
- 上传者