Biswa and GCD
All submissions for this problem are available.
Biswa has an array A[ ] consisting of N integers.
He loves prime numbers, so he wants to calculate the value of the following function for his array:
F(A) = number of non-empty sub-sequences of A[ ] such that gcd of all numbers in that sub-sequence is a power of a prime number, i.e p^e for some prime p and e>=1.
Note: sub-sequences consisting of equal numbers occurring at different positions are considered different. (example: Array [2,2,2] has 7 non-empty sub-sequences)
However, Biswa's mischievous little brother Debu repeatedly makes some changes to the array. In each change, he selects an element of the array, and sets it to a new (or possibly same) value Y.
Help Biswa calculate F(A) after each change.
The first line of Input consists of an integer T specifying the number of test cases. The description of T test cases follows:
The First line of each test case consists of two space separated integers, N and Q, the number of elements in Biswa's array, and number of changes performed by Debu on the array.
The next line contains N space separated integers A , A , ... , A[N]
Q lines follow, each line specifying a change, which is of the form:
denoting Xth element of array is set to the value Y.
For each test case, output Q lines, each containing the value of F(A) modulo 1000000007 ( 10^9 + 7 )
- 1 ≤ T ≤ 3
- 1 ≤ N ≤ 100000
- 1 ≤ A[i] ≤ 1000000
- 1 ≤ Q ≤ 100000
- 1 ≤ X ≤ N
- 1 ≤ Y ≤ 1000000
Input: 2 3 2 2 4 8 1 2 1 5 1 1 2 1 1 Output: 7 4 0 Warning: Large Input data. Use faster input methods.
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA|
Fetching successful submissions