D-Function

題目描述

Let $D(n)$ represent the sum of digits of $n$. For how many integers $n$ where $10^l\le n<10^r$ satisfy $D(k?n)=k?D(n)$? Output the answer modulo $10^9+7$.

輸入描述

The first line contains an integer $t$ ($1\le t\le 10^4$) – the number of test cases.

Each test case contains three integers $l$, $r$, and $k$ ($0\le l<r\le 10^9$, $1\le k\le 10^9$).

輸出描述

For each test case, output an integer, the answer, modulo $10^9+7$.

提示

For the first test case, the only values of $n$ that satisfy the condition are $1$ and $2$.

For the second test case, the only values of $n$ that satisfy the condition are $1$, $10$, and $11$.

For the third test case, all values of $n$ between $10$ inclusive and $100$ exclusive satisfy the condition.

題面翻譯

令 $D(n)$ 代表 $n$ 各個數位上數字之和。求：有多少個 $n$ 滿足 $10^l\le n<10^r$ 且 $D(k?n)=k?D(n)$？答案對 $10^9+7$ 取模。

樣例 #1

樣例輸入 #1

6
0 1 4
0 2 7
1 2 1
1 2 3
582 74663 3
0 3 1

樣例輸出 #1

2
3
90
12
974995667
999

原題

Codeforces——傳送門
洛谷——傳送門

思路

對于 $D(k?n)=k?D(n)$，我們觀察可以得到 左式一定小于等于右式。因為右式是對每一位數字都乘以 $k$ 再相加，左式對 $n$ 中每一位數字乘以 $k$ 后要先處理進位再相加，而每發生一次進位都會導致最后得到的和少了 $10$。所以如果要滿足 $D(k?n)=k?D(n)$，則 $k$ 乘以每一位都不能 $\ge 10$，即對于 $n$ 中的任意一位數字 $x$，需滿足 $x?k\le 9$。

因為 $x?k\le 9$，所以對于 $n$ 的每一位，若該位為最高位，則 $x$ 不能為 $0$，可滿足的位數字有 $\frac{k}{9}$ 種；若該位不為最高位，則可滿足的位數字有 $\frac{k}{9}+1$ 種。因此對于 $10^i\le n<10^{i+1}$，滿足條件的 $n$ 的個數有 $\frac{k}{9}?(\frac{k}{9}+1{)}^i$ 個。那么答案就是 $\frac{k}{9}?(\frac{k}{9}+1{)}^{r?1}?\frac{k}{9}?(\frac{k}{9}+1{)}^{l?1}$，利用等比數列求和公式化簡得 $(\frac{k}{9}+1{)}^r?(\frac{k}{9}+1{)}^l$。當然也可以不化簡直接計算結果。

代碼

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;const i64 mod = 1e9 + 7;
// 快速冪
i64 qpow(i64 a, i64 b, i64 c)
{i64 ans = 1;a %= c;while (b){if (b & 1){ans = (ans * a) % c;}a = (a * a) % c;b >>= 1;}return ans % c;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);int t;cin >> t;while (t--){i64 l, r, k;cin >> l >> r >> k;i64 num = 9 / k + 1;cout << (qpow(num, r, mod) - qpow(num, l, mod) + mod) % mod << '\n';}return 0;
}