Блог пользователя HVCYM

Need help !!!
Автор HVCYM, история, 6 часов назад, По-английски

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??

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
6 часов назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 :) )

→ Ответить
  • »
    »
    6 часов назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Thanks for the suggestion but these two are different problems

    → Ответить
»
5 часов назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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!

→ Ответить