IITKWPCM - Coprime Again
As You had known upto now that Feluda is very good in mathematics, Now he decided to understand the properties of coprime numbers. Two numbers are called coprime if greatest common divisor of those numbers is 1. One day feluda was reading mysterious book in which he found this problem.
For a given positive integer n, Find out product of all the numbers from 1 to n excluding those which are not coprime to n. As this product can grow very large and Feluda being a small child gets scared from large numbers. Hence he wants that you should output the product modulo n.
Help little Feluda to solve this problem.
T : number of test cases. (T >= 1 && T <= 10^4)
For next T lines, you are given an integer n such that 1 <= n <= 10 ^ 18.
For each test case, output one line as stated in the problem statement.
For Who are going TLE and want to solve easier version. Please go to http://www.spoj.com/problems/IITKWPCQ/
Finally on top.Last edit: 2014-12-19 17:01:40
@kewlcoder, there is no ambiguity in the problem statement regarding that case, you should be able to know the answer by understanding the problem.
I suppose the answer for n=1 is 0. Can you please confirm?