Codeforces Codecraft 20 Prob C

Can somebody please tell me how to solve this problem from Codeforces Div 2 Contest.
https://codeforces.com/contest/1316/problem/C
Thank you.

Just find the smallest power of a that doesn’t divide p and the smallest power of b, and add the two.After some thinking, it will become trivial why.

1 Like

Thanks a lot for the reply but thing is that I had already read the editorial for this but was not able to understand how this is true. If you can explain as to why this thing works it would be really helpful.

let’s say those were i and j, the least power of a and b that aren’t a multiple of p.
Now the power of i + j=
a[0] * b[i+j] + a[1] * b[i+j-1]… a[i+j] * b[0].
since a[0] to a[i-1] are a multiple of of p and b[0] to b[j-1] are a multiple of p, all terms except a[i]* b[j] are multiples of p. We know a[i] & b[j] aren’t multiples of p, therefore a[i]*b[j] doesn’t divide p. Therefore the power i+j doesn’t divide p.

1 Like

Ohhhhh… I think I just got it. Thanks a lot for the wonderful expalanation

1 Like
1 Like