Codeforces--1213C--Book Reading

63 阅读 0 评论 42 点赞

我是靠谱客的博主拉长小霸王，最近开发中收集的这篇文章主要介绍Codeforces--1213C--Book Reading，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述：
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
题意：
Polycarp正在读一本有n页编号的书，编号从1到n。每当他看完能被m整除数字的页面时，他都会记下此页码的最后一位数字。例如，如果n = 15且m = 5，则可被m整除的页面为5,10,15。他们的最后数字相应地为5,0,5，其总和为10。你的任务是计算Polycarp写下的所有数字的总和。您必须回答q个独立查询。
题解：
找规律，找循环节。a数组就是从0-9的循环节，然后瞎搞算一下就好了
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int a[15][15] = {
{0},
//0
{1,2,3,4,5,6,7,8,9,0},
//1
{2,4,6,8,0},
//2
{3,6,9,2,5,8,1,4,7,0},
//3
{4,8,2,6,0}, //4
{5,0}, //5
{6,2,8,4,0}, //6
{7,4,1,8,5,2,9,6,3,0}, //7
{8,6,4,2,0}, //8
{9,8,7,6,5,4,3,2,1,0}, //9
};
int b[100] = {1,10,5,10,5,2,5,10,5,10};
typedef long long ll;
ll n,m;
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%I64d%I64d",&n,&m);
if(n < m){
printf("0n");
continue;
}
ll k = n / m;
ll x = m % 10;
//cout<<x<<endl;
ll t = k / b[x];
ll y = k % b[x];
ll sum = 0;
for(int i = 0; i < 15; i ++){
sum += a[x][i];
}
sum *= t;
for(int i = 0; i < y; i ++){
sum += a[x][i];
}
printf("%I64dn",sum);
}
return 0;
}