Algorithm
Polycarp is reading a book consisting of n pages numbered from 1 to n. Every time he finishes the page with the number divisible by m, he writes down the last digit of this page number. For example, if n=15 and m=5, pages divisible by m are 5,10,15. Their last digits are 5,0,5 correspondingly, their sum is 10.
Your task is to calculate the sum of all digits Polycarp has written down.
You have to answer q independent queries.
The first line of the input contains one integer q (1≤q≤1000) — the number of queries.
The following q lines contain queries, one per line. Each query is given as two integers n and m (1≤n,m≤1016) — the number of pages in the book and required divisor, respectively.
For each query print the answer for it — the sum of digits written down by Polycarp.
7 1 1 10 1 100 3 1024 14 998244353 1337 123 144 1234312817382646 13
1 45 153 294 3359835 0 427262129093995
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
int const N = 1e6 + 1;
int q;
long long n, m;
int main() {
#ifndef ONLINE_JUDGE
freopen("in", "r", stdin);
#endif
scanf("%d", &q);
while(q-- != 0) {
scanf("%lld %lld", &n, &m);
if(m > n) {
puts("0");
continue;
}
vector<int> all;
for(long long i = m; i <= n; i += m) {
if(i != m && all[0] == i % 10)
break;
all.push_back(i % 10);
}
long long res = 0;
for(int i = 0; i < all.size(); ++i)
res += all[i];
long long mm = m * all.size();
res = n / mm * res;
long long rem = n % mm;
for(int i = 0; i < all.size(); ++i) {
if(rem - m < 0)
break;
res += all[i];
rem -= m;
}
printf("%lld\n", res);
}
return 0;
}Input
1 1
10 1
100 3
1024 14
998244353 1337
123 144
1234312817382646 13
Output
45
153
294
3359835
0
427262129093995
Demonstration
Codeforcess Solution C. Book Reading -Solution in C, C++, Java, Python ,Book Reading,Codeforcess Solution