A97904.皓仔的累乘
入门
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
皓仔不喜欢数字 a ,具体来说他不喜欢数字表示数位中包含数字 a 或能被 a 整除的所有数。
皓仔从 1 累乘到 n,但他会避开他不喜欢的数字:凡是数位中包含数字 a 或 能被 a 整除的所有数,一律跳过不进行累乘。
例如: 假若皓仔不喜欢数字7,那么他就会跳过数位中包含数字 7 或 能被 7 整除的所有数不进行累乘。
求剩余数的累乘乘积, 由于数字可能太大,结果对 109+7 取模。
输入格式
输入一行两个整数 n,a, 代表累乘的范围,以及皓仔不喜欢的数字。
输出格式
输出一行一个整数,表示累乘结果,结果对 109+7 取模。
输入输出样例
输入#1
5 3
输出#1
40
说明/提示
【样例解释】
样例一中不喜欢的数字是 3,跳过后的算式为 1×2×4×5=40。
如果输入为 6 3,由于 6 是能被 3 整除的数,结果同样为 40。
如果输入为 5 2,则算式变为 1×3×5=15,跳过数位包含 2 和能被 2 整除的数。
【数据范围】
对于所有测试数据保证:2≤n≤2⋅105 , 2≤a≤9 。
| 测试点 | n≤ |
|---|---|
| 1∼3 | 1000 |
| 4∼10 | 2⋅105 |