HVCYM's blog

Need help !!!
By HVCYM, history, 6 hours ago, In English

Need help with the following problem :

Given an array of n integers. Count the number subsequence whose product is divisible by k. Return answer modulo 1E9 + 7.

1 <= n <= 1E5 1 <= k < 1E9 1 <= a[i] <= 1E9

I think idea is use to prime factorization but I am not able to get it completely. Is there any concept that I must learn??

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
6 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

https://codeforces.net/problemset/problem/577/B you can look this problems editorial I think this the same problem which you described ( I hope you upvote :) )

→ Reply
  • »
    »
    6 hours ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks for the suggestion but these two are different problems

    → Reply
»
5 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I recommend approaching this problem using the two-pointer technique. Here are some key insights to consider:

  • If you have a range [l,r] that is divisible by K, then both [l, r+1] and [l-1, r] should also be divisible by K.
  • Consider the number of subsequences when you increment r by 1.
  • The maximum number of subsequences occurs when a[i] = K for all i from 1 to n. Determine what that number is.

I hope this information is helpful!

→ Reply