SHARE

TWEET

# Untitled

a guest
Jul 21st, 2019
245
Never

**Not a member of Pastebin yet?**

**, it unlocks many cool features!**

__Sign Up__- 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
- Inputs:
- First line contains two space-separated integers N and M
- Next M lines contain three space-separated integers Li , Ri , Gi
- Output:
- The number of arrays satisfying the requirements.Since the answer can be too big,print it modulo 1000000007.
- Constraints:
- 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
- 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.