#PQJ210x4129. QOJ 210_4129

    ID: 2775 传统题 3000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SDOI 2013排序

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