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

Question

One of my friends got this question in google coding contest. Here goes the question.

Find the number of N-digit numbers that are divisible by both X and Y. Since the answer can be very large, print the answer modulo 10^9 + 7.

Note: 0 is not considered single-digit number.

Input: N, X, Y.

Constraints:

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

Eg-1 :
N = 2, X = 5, Y = 7
output : 2 (35 and 70 are the required numbers)

Eg-2 :
N = 1, X = 2, Y = 3
output : 1 (6 is the required number)

If the constraints on N were smaller, then it would be easy (ans = 10^N / LCM(X,Y) - 10^(N-1) / LCM(X,Y)).

But N is upto 1000, hence I am unable to solve it.

Answer 1

This question looks like it was intended to be more difficult, but I would do it pretty much the way you said:

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

The trick is to calculate the terms quickly.

Let M = LCM(X,Y), and say we have:

10^a = Mq_a + r_a, and

10^b = Mq_b + r_b

The we can easily calculate:

10^a+b = M(Mq_aq_b + r_aq_b + r_bq_a + floor(r_ar_b/M)) + (r_ar_b%M)

With that formula, we can calculate the quotient and remainder for 10^N/M in just 2 log N steps using exponentiation by squaring: https://en.wikipedia.org/wiki/Exponentiation_by_squaring