a guest Jul 21st, 2019 245 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
- Constrained GCD Array
- 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:
- Li Ri Gi, i.e., For every pair of consecutive elements in the range [Li , Ri] in the array, the GCD is Gi .
- 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).
- It is guaranteed that no two query ranges([L i , R i ]) intersect.
- Here GCD denotes greatest common divisor
- First line contains two space-separated integers N and M
- Next M lines contain three space-separated integers Li , Ri , Gi
- The number of arrays satisfying the requirements.Since the answer can be too big,print it modulo 1000000007.
- 1 <= N <= 10 9
- 1 <= M <= 100
- 1 <= L i < R i <= N
- 1 <= G i <= 20
- Sample Input
- 3 1
- 1 2 2
- Sample Output
RAW Paste Data