IITKWPCB - Check the coprimeness
Find largest non-negative number less than or equal to floor (N/2) which is coprime to N.
Two number a and b are considered to coprime if gcd(a, b) = 1.
Input
T : number of test cases (T ≤ 1000).
For next T lines, every line contains n (1 ≤ n ≤ 1012).
Output
For each test case, output the answer as described in the problem statement.
Example
Input: 4
3
4
5
100
Output: 1
1
2
49
hide comments
|
ayushgupta1997:
2017-06-18 19:50:59
simple just think for even and odd numbers
|
|
sandeep_4141:
2017-06-15 23:07:44
easy one !!
|
|
sushanth_r:
2017-04-23 14:29:09
AC in one go with O(1). Simple if else =) |
|
sudeep_11:
2017-01-24 15:41:06
No need to calculate GCD, just find out the pattern ! |
|
arindam1234:
2017-01-02 08:29:40
AC in 1 Go!!! My 50th... |
|
mayanksat:
2016-06-09 14:06:08
@ragwave thanks your comment helped ; simple if else implementation. |
|
farhan764:
2016-01-19 21:37:41
python rocks......jus import gcd.... |
|
ragwave:
2016-01-01 21:14:02
jst write down numbers from 30 to 40 on a paper,and study the answer pattern.......its jst if/else problem!!
|
|
Shashank Tiwari:
2015-12-16 10:57:32
Gcd(0,N) = N . So, for N= 1 , Gcd(0,1)=1 . |
|
Pulkit Mittal:
2015-12-06 17:03:56
must use if else |
| Added by: | praveen123 |
| Date: | 2013-08-05 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | IITK ACA CSE online judge |
RSS