What are the best strategies for C. Book Reading in Codeforces Round contests?

本文共计649个文字，预计阅读时间需要3分钟。

Polycarp在阅读一本有n页的书，页码从1到n。每次翻到页码能被m整除的页时，他就记下这个页码的最后一位数字。例如，如果n=15，那么他会记录下哪些页码的最后一位数字？

Polycarp is reading a book consisting ofn">nnpages numbered from1">11ton">nn. Every time he finishes the page with the number divisible bym">mm, he writes down the last digit of this page number. For example, ifn=15">n=15n=15andm=5">m=5m=5, pages divisible bym">mmare5,10,15">5,10,155,10,15. Their last digits are5,0,5">5,0,55,0,5correspondingly, their sum is10">1010.

Your task is to calculate the sum of all digits Polycarp has written down.

You have to answerq">qqindependent queries.

Input

The first line of the input contains one integerq">qq(1≤q≤1000">1≤q≤10001≤q≤1000) — the number of queries.

The followingq">qqlines contain queries, one per line. Each query is given as two integersn">nnandm">mm(1≤n,m≤1016">1≤n,m≤10161≤n,m≤1016) — the number of pages in the book and required divisor, respectively.

Output

For each query print the answer for it — the sum of digits written down by Polycarp.

Example input Copy

7 1 1 10 1 100 3 1024 14 998244353 1337 123 144 1234312817382646 13 output Copy

1 45 153 294 3359835 0 427262129093995

---

分析：计算出n范围内m的个位数的倍数的个位数的和

---

#include <bits/stdc++.h> #define TOP 10001 using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(0); cin.tie(0); map<int, vector<int> > r; int q; ll m, n, coc, rest, fin, ans; vector<int> aux; r[1] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}; r[2] = {2, 4, 6, 8, 0}; r[3] = {3, 6, 9, 2, 5, 8, 1, 4, 7, 0}; r[4] = {4, 8, 2, 6, 0}; r[5] = {5, 0}; r[6] = {6, 2, 8, 4, 0}; r[7] = {7, 4, 1, 8, 5, 2, 9, 6, 3, 0}; r[8] = {8, 6, 4, 2, 0}; r[9] = {9, 8, 7, 6, 5, 4, 3, 2, 1 ,0}; cin >> q; while(q--){ cin >> n >> m; coc = n / m; fin = m % 10; ans = 0; if(fin != 0){ aux = r[fin]; n = aux.size(); rest = coc % n; coc /= n; for(int i = 0; i < n; ++i) ans += aux[i] * (coc + (i < rest)); } cout << ans << ‘\n‘; } return 0; }