Codeforces Round #725 (Div. 3)F. Interesting Function
给两个数字l和r, 求从l加到r中间digit的变化个数是多少.
这题用的方法和D一样,就是先求R的答案, 然后减去L的答案, 具体的求法是通过观察: 比如21这个数, 从1->9 是9个1位改变, 9->10是1个2位, 10->19是9个1位改变, 19->20是2个1位改变. 20->21 是1个1位改变, 所以加起来就是21+2, 有次可推,数字123是123+12+1.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); int t; cin >> t; while (t --) { int l,r; cin >> l >> r; auto count = [&](int n) -> int64_t { int base = 10; int digit = 1; int64_t res = 0; while (n) { res += n; n /= base; } return res; }; cout << count(r) - count(l) << endl; } return 0; } |