#PQJ210x4129. QOJ 210_4129
QOJ 210_4129
全国青少年信息学奥林匹克
山东省省队选拔赛2013 第一轮
第二试
淘金
淘金
【问题描述】
小Z 在玩一个叫做《淘金者》的游戏。游戏的世界是一个二维坐标。X 轴、
Y 轴坐标范围均为1..N。初始的时候,所有的整数坐标点上均有一块金子,共
N*N 块。
一阵风吹过,金子的位置发生了一些变化。细心的小Z 发现,初始在(i, j)
坐标处的金子会变到(f(i), f(j))坐标处。其中f(x)表示x 各位数字的乘积,例如
f(99)=81,f(12)=2,f(10)=0。如果金子变化后的坐标不在1..N 的范围内,我们认
为这块金子已经被移出游戏。同时可以发现,对于变化之后的游戏局面,某些坐
标上的金子数量可能不止一块,而另外一些坐标上可能已经没有金子。这次变化
之后,游戏将不会再对金子的位置和数量进行改变,玩家可以开始进行采集工作。
小Z 很懒,打算只进行K 次采集。每次采集可以得到某一个坐标上的所有
金子,采集之后,该坐标上的金子数变为0。
现在小Z 希望知道,对于变化之后的游戏局面,在采集次数为K 的前提下,
最多可以采集到多少块金子?
答案可能很大,小Z 希望得到对1000000007(109+7)取模之后的答案。
【输入格式】
共一行,包含两个正整数N, K。
【输出格式】
一个整数,表示最多可以采集到的金子数量。
【样例输入】
12 5
【样例输出】
18
全国青少年信息学奥林匹克
山东省省队选拔赛2013 第一轮 第二试 淘金 【样例说明】 1 2 3 4 5 6 7 8 9 10 11 12 ---------------------------------- 1|4 4 2 2 2 2 2 2 2 0 0 0 2|4 4 2 2 2 2 2 2 2 0 0 0 3|2 2 1 1 1 1 1 1 1 0 0 0 4|2 2 1 1 1 1 1 1 1 0 0 0 5|2 2 1 1 1 1 1 1 1 0 0 0 6|2 2 1 1 1 1 1 1 1 0 0 0 7|2 2 1 1 1 1 1 1 1 0 0 0 8|2 2 1 1 1 1 1 1 1 0 0 0 9|2 2 1 1 1 1 1 1 1 0 0 0 10|0 0 0 0 0 0 0 0 0 0 0 0 11|0 0 0 0 0 0 0 0 0 0 0 0 12|0 0 0 0 0 0 0 0 0 0 0 0 变化之后每个坐标上金子的数量如上。 可以依次采集(1, 1)、(1, 2)、(2, 1)、(2, 2)、(3, 1)上的金子,共18 块。 【数据规模和约定】
测试点编号 N K 1 N≤1000 K≤100000 2 3 N≤1000000 4 5 N=1012 6 7 N≤1012 K=1 8 9 K≤100000 10
对于100%的测试数据:K≤N2