SHARE
TWEET

Untitled

a guest Jul 21st, 2019 245 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Constrained GCD Array
  2.  
  3. Find the number of arrays of size N where each element of the array is in between 1 to 20, and that satisfy M requirements of the form:
  4. Li Ri Gi, i.e., For every pair of consecutive elements in the range [Li , Ri] in the array, the GCD is Gi .
  5. For example, a query of the form 3 6 5 means that gcd(A 3 , A 4 ) = gcd(A 4 , A 5 ) = gcd(A 5 , A 6 ) = 5 where A is the array and Ai denotes the i-th element of the array(1-based indexing).
  6.  
  7. It is guaranteed that no two query ranges([L i , R i ]) intersect.
  8.  
  9. Here GCD denotes greatest common divisor
  10.  
  11. Inputs:
  12. First line contains two space-separated integers N and M
  13. Next M lines contain three space-separated integers Li , Ri , Gi
  14.  
  15. Output:
  16. The number of arrays satisfying the requirements.Since the answer can be too big,print it modulo 1000000007.
  17.  
  18. Constraints:
  19. 1 <= N <= 10 9
  20. 1 <= M <= 100
  21. 1 <= L i < R i <= N
  22. 1 <= G i <= 20
  23.  
  24. Sample Input
  25. 3 1
  26. 1 2 2
  27.  
  28. Sample Output
  29. 1260
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top