首页 > 其他 > 详细

C. Book Reading (Codeforces Round #582 (Div. 3))

时间:2019-09-13 22:12:37      阅读:186      评论:0      收藏:0      [点我收藏+]

Polycarp is reading a book consisting of nn pages numbered from 11 to nn. Every time he finishes the page with the number divisible by mm, he writes down the last digit of this page number. For example, if n=15n=15 and m=5m=5, pages divisible by mm are 5,10,155,10,15. Their last digits are 5,0,55,0,5 correspondingly, their sum is 1010.

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

You have to answer qq independent queries.

Input

The first line of the input contains one integer qq (1q10001≤q≤1000) — the number of queries.

The following qq lines contain queries, one per line. Each query is given as two integers nn and mm (1n,m10161≤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;
}

 

 


 

C. Book Reading (Codeforces Round #582 (Div. 3))

原文:https://www.cnblogs.com/Shallow-dream/p/11517777.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!