×

# SEALCM - Editorial

Author: Sergey Nagin
Editorialist: Lalit Kundu

MEDIUM-HARD

# PRE-REQUISITES:

Solving Dynamic Programming with Matrix Expo

# PROBLEM:

In this problem Sereja is interested in number of arrays A[1], A[2], ..., A[N] (1 ≤ A[i] ≤ M, A[i] - integer) such that least common multiple (LCM) of all its elements is divisible by number D.

Please, find sum of answers to the problem with D = L, D = L+1, ..., D = R. As answer could be large, please output it modulo (109 + 7).

# TECHNIQUE:

Let there be K states, s1,s2...sK.
For each state si where i = 1 to K recurrence is defined as:
f(n,si) = sum {j=1 to K} c{i,j} f(n-1,sj).
We define a transition matrix M where M[i][j]=c{i,j}.
Let's consider M{N-1}. Sum of all elements in row i will give us f(N,si) assuming f(0,i)=0 forall i.

# EXPLANATION:

Let's solve for a single D first. Let's say D has prime factors p1a1, p2a2 ... pKaK, where all pi are unique.
We form a simple dp of dp[n,mask], which denotes the answer for N=n and D=product [pia_i], if i'th bit is set in mask. So, mask is a K bit number.
A simple recurrence would be:

&ret = dp[n,mask]
primes[] //prime factors of D.
count[] //count[i] denotes count of i'th prime in D
ret=0
for i = 0 to size(primes)-1:
for j = 1 to M:
//if j is kept at n'th index
//and keeping it satisfies the i'th set bit condition
//ie. count of primes[i] in j is greater than or equal to count[i]
if count_prime(primes[i] in j) >= count[i]
//set the i'th bit, add to current ret


So, we can clearly see that our dp[n,x] is dependent on dp[n-1,y], where x and y are two different masks/states. We can use matrix exponentiation here because in one state in our dp, answer for n is dependent on answer for n-1 and the transition among other states is not dependent on n.

So, we form the transition matrix, where we set at transit[i][j], the number of ways to reach mask j from mask i . Sum of all elements in (2K-1)'th (all bits of D are set) row of N-1'th power of this transition matrix, will give us the answer, in accordance with the technique explained above. Try to prove how this works.

So, complexity for single D is O(log N * (2K*3)). Note matrix multiplication of sizes P*P takes O(P3). And, maximum K is until 235711*13... is smaller than 1000(since D<1000). So, max K is 4. Total complexity for single D is O(log N * 212).

Doing it for 1000 such values of D will take O(log N * 222) worst case. Note it will be really lower than that because of variation in K.

# SOLUTIONS:

This question is marked "community wiki".

3.0k93163187
accept rate: 12%

 16 This problem can be solved easily with inclusion exclusion principal too . http://www.codechef.com/viewsolution/5846988 Heres my solution . First factorize all the numbers in the form d = p * q * r * s where p,q,r and s are powers of prime numbers . Do this for all numbers from L to R . Then apply inclusion exclusion . See the code for more understanding answered 12 Jan '15, 16:00 1.0k●1●12 accept rate: 4% exactly what i did.. (12 Jan '15, 16:55) The constraints were low enough to use IEP for at max '4' elements. (12 Jan '15, 19:45)
 3 Inclusion Exclusion. Helped by a pen and lots of paper. Time Complexity is O(log(n)*2^15). That's almost 250 times faster than required. Made me wonder for a long time if I was missing something. http://www.codechef.com/viewsolution/5867632 answered 13 Jan '15, 00:43 4★gkcs 2.6k●1●11●27 accept rate: 9%
 3 Another Inclusion Exclusion guy here. Having used python, I did not have to hard-code for different number of factors. from itertools import combinations FTFW xD http://www.codechef.com/viewsolution/5835895 answered 13 Jan '15, 09:28 737●2●11 accept rate: 16%
 1 Any idea someone how to use the fact, that N, M <= 10? Brute force worked fine for test cases, but I didn't try for 10^10... answered 13 Jan '15, 17:44 16.9k●49●115●225 accept rate: 11% 1 To explore N, M <= 10 we can use a simple dynamic programming algorithm. First, note that the maximum LCM of an array with numbers 1..10 is 2520 (5 * 7 * 8 * 9). So our search state will be how many arrays are there with X numbers and lcm L. This yields 10*2520 states and we need to check all numbers 1..N and all lcms 1..2520. (13 Jan '15, 23:38) mogers5★ Thanks ;-) (13 Jan '15, 23:49)
 1 Hi I can't open neither setter's solution nor tester solution, can you please check this links. Thanks. answered 21 Jan '15, 00:05 11●1●2 accept rate: 0%
 1 can anyone explain the editorial for newbies like me so that we can progress further, im not getting anything in the editorial as i dont know anything about bit masks. link This answer is marked "community wiki". answered 27 May '15, 17:39 198●1●5 accept rate: 0%
 0 The solution links of setter and tester are not working. Can you please check that? answered 21 Jan '15, 14:28 2★loch_ish 26 accept rate: 25%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,026
×1,897
×1,172
×260
×204
×10

question asked: 12 Jan '15, 15:08

question was seen: 7,865 times

last updated: 27 May '15, 17:39