bzoj#P2326. [HNOI2011] 数学作业

[HNOI2011] 数学作业

题目描述

小 C 数学成绩优异,于是老师给小 C 留了一道非常难的数学作业题:

给定正整数 n,mn,m,要求计算 Concatenate(n)mod m\mathrm{Concatenate}(n) \bmod \ m 的值,其中 Concatenate(n)\mathrm{Concatenate}(n) 是将 1n1 \sim n 所有正整数 顺序连接起来得到的数。

例如,n=13n = 13 , Concatenate(n)=12345678910111213\mathrm{Concatenate}(n) = 12345678910111213。小C 想了大半天终于意识到这是一道不可能手算出来的题目,于是他只好向你求助,希望你能编写一个程序帮他解决这个问题。

输入格式

一行两个正整数 n,mn,m

输出格式

输出一行一个整数表示答案。

13 13
4

数据规模与约定

对于 30%30\% 的数据,1n1061\le n \le 10^6
对于 100%100\% 的数据,1n10181\le n \le 10^{18}1m1091\le m \le 10^9

提示

没有写明提示

题目来源

没有写明来源(题面来自洛谷)