DETER2 - Find The Determinant II
In this problem you have to calculate the determinant of an N x N matrix whose entries are given by m[i][j] = gcd(i,j)k, 1 ≤ i,j ≤ N.
Here gcd(i,j) denotes the greatest common divisor of i and j.
As the determinant D can grow very large, you have to print D%1000003.
First line of input consists of a single integer containing the number of test cases T ( equal to around 20), each of the following T lines contain two integers N and k where N is the size of the matrix and k is the exponent.
1 ≤ N ≤ 1000000
1 ≤ k ≤ 109
One line corresponding to each test case containing the determinant modulo 1000003 for the corresponding test case.
Input: 3 4 2 2 4 4 3 Output: 288 15 10192Note: You may want to solve DETER first, in case you havent already solved it.
There's something very strange with input ; I shouldn't get 0.33 on sub_11598340. ???
abhijith reddy d:
So many pointless optimizations are needed :-/
what is the hell of the optimization?
Heavy optimizations needed.
time is strict for this problem? 1s?