数论之模加法运算

2019-04-13 11:52发布

站内文章 / 模拟电子
11959 0 1417
class="markdown_views prism-github-gist">

问题

一个m位的整数，有多少可以被整数n整除？其中m可以大于15。
  • 测试输入
    1 3
  • 测试输出
    4

分析1

这个问题显然不能穷举所有的情况。数论中的模加法运算有这样的性质（对乘法也是一样）： (a+b) mod n===(a mod n+b mod n) mod n(a mod n+b) mod n(a+b mod n) mod n 由此可见，一个数的取模问题可以拆分成两个求和数的取模问题，这显然属于动态规划能够解决的问题。对于一个m位的整数x，可以将其按照十进制拆解为x=x0×10m−1+x1×10m−2+⋯+xm−2×10+xm−1。对于其中的i−1和i位做如下分析：
令j=xi−1 mod n，则
(xi−1×10+xi) mod n====[(xi−1×10) mod n+xi] mod n{[(xi−1 mod n)×10] mod n+xi} mod n[(j×10) mod n+xi] mod n(j×10+xi) mod n 由此定义c[i,j]为前i位数模n余数为j的个数，原问题为c[m,0]。第i位的取值k=0∼9，穷举一遍后前i位余数为(j∗10+k)%n的个数，等于前i−1位余数为j的个数的累计和。从而递归式为 {c[0,0]=1,c[i,j]=0,c[i,(j∗10

热门文章