问题 5909 --NOI2011湖北省选 一试 第1题 数学作业

5909: NOI2011湖北省选 一试 第1题 数学作业

时间限制: 1 Sec  内存限制: 512 MB
提交: 3  解决: 3
[提交][状态][讨论版][数据上传:][下载FPS1元][添加到购物车][下载测试数据1元][92kb]

题目描述

小C数学成绩优异,于是老师给小C留了一道非常难的数学作业题: 给定正整数N和M,要求计算Concatenate (1 .. N) Mod M的值,其中Concatenate (1 .. N)是将所有正整数1, 2, …, N顺序连接起来得到的数。例如,N = 13, Concatenate (1 .. N) = 12345678910111213. 小C想了大半天终于意识到这是一道不可能手算出来的题目,于是他只好向你求助,希望你能编写一个程序帮他解决这个问题。

输入

  输入只有一行且为用空格隔开的两个正整数N和M,其中30%的数据满足1≤N≤1000000;100%的数据满足1≤N≤1018且1≤M≤109.

输出

  输出仅包含一个非负整数,表示Concatenate (1 .. N) Mod M的值。

样例输入

13 13

样例输出

4

提示

来源

[提交][状态]