可被给定两个数字整除的 N 位数字的个数

Question

我的一个朋友在 google 编码竞赛 中得到了这个问题。问题来了。

求出能同时被 X 和 Y 整除的 N 位数字的个数。由于答案可能非常大，打印答案模 10^9 + 7.

注意：0不被认为是个位数。

输入： N、X、Y。

约束条件：

1 <= N <= 10000
1 <= X,Y <= 20

例如-1 :
N = 2, X = 5, Y = 7
输出 : 2（35和70是必需的数字）

例如-2 :
N = 1, X = 2, Y = 3
输出 : 1（6是必需的数字）

如果对 N 的约束较小，那么它会很容易 (ans = 10^N / LCM(X,Y) - 10^(N-1) / LCM(X,Y))。

但是N高达1000，所以我无法解决。

Answer 1

这道题看起来是为了更难，但我会按照你说的做：

ans = floor((10^N-1)/LCM(X,Y)) - floor((10^N-1-1)/LCM(X,Y))

诀窍是快速计算项。

令 M = LCM(X,Y)，并假设我们有：

10^a = Mq_a + r_a, and

10^b = Mq_b + r_b

我们可以很容易地计算出：

10^a+b = M(Mq_aq_b + r_aq_b + r_bq_a + 地板（r _ar_b/M)) + (r_ar_b%M)

使用该公式，我们可以使用平方取幂计算 10^N/M 的商和余数，仅需 2 log N 步：https://en.wikipedia.org/wiki/Exponentiation_by_squaring

Answer 2

以下 python 适用于此问题，

import math
MOD  = 1000000007

def sub(x,y):
    return (x-y+MOD)%MOD

def mul(x,y):
    return (x*y)%MOD


def power(x,y):
    res = 1
    x%=MOD
    while y!=0:
        if y&1 :
            res = mul(res,x)
        y>>=1
        x = mul(x,x)
        
    return res
        
def mod_inv(n):
    return power(n,MOD-2)

x,y = [int(i) for i in input().split()]

m = math.lcm(x,y)
n = int(input())
a = -1
b = -1
total = 1
for i in range(n-1):
    total = (total * 10)%m
b = total % m
total = (total*10)%m
a = total % m

l = power(10 , n-1)
r = power(10 , n)

ans = sub( sub(r , l) , sub(a,b)   )
ans = mul(ans , mod_inv(m))

print(ans)

这个问题的方法非常简单，

设，m = lcm(x,y)

让， 10^n -1 = m*x + a

10^(n-1) -1 = m*y + b

现在从上面的两个等式很明显我们的答案等于 (x - y)%MOD .

所以，

(x-y) = ((10^n - 10^(n-1)) - (a-b)) / m

还有，a = (10^n)%m 和 b = (10^(n-1))%m

使用简单的模运算规则，我们可以在 O(n) 时间内轻松计算出 a 和 b。

同样对于公式中的减法和除法，我们可以分别使用模减法和除法。

注：(a/b)%MOD = ( a * (mod_inverse(b, MOD)%MOD )%MOD

可被给定两个数字整除的 N 位数字的个数

Number of N-digit numbers that are divisible by given two numbers

algorithm

time-complexity

largenumber