SPOJ.com - Problem IITKWPCB

IITKWPCB - Check the coprimeness

#ad-hoc-1

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.

T : number of test cases (T ≤ 1000).

For next T lines, every line contains n (1 ≤ n ≤ 10¹²).

For each test case, output the answer as described in the problem statement.

Input:
4
3
4
5
100 

Output:
1
1
2
49

< Previous 1 2 3 4 Next >

	awas_mohan2021: 2023-05-02 21:18:06 think brutforce better
	lokesh_2052: 2021-02-26 12:23:06 <snip> Please correct if i'am wrong [NG]: It's wrong to spoil. Last edit: 2021-02-26 16:15:15
	davidgalehouse: 2019-02-01 04:59:02 Don't worry about n==1 case.
	anurag_018: 2018-12-25 15:30:24 ac in one go
	satyamlal2209: 2018-06-30 17:20:57 Just make sure that if you are using C you might keep getting a wrong answer even though your logic might be correct because of the incorrect data type. Use unsigned long long int and also while using printf, try using inttype.h library! otherwise,core logic is simple.
	ameyanator: 2018-03-01 20:56:21 Easy Question. At first I just ran a loop to find the GCD=1 condition it passed (had guessed that we'll always have an answer) but then the comments provided with another approach the pattern approach which was too easy to code :)
	karthik_vg: 2018-01-04 14:51:29 brute force it and get the pattern and then its O(1)
	sanyam19: 2017-11-07 09:38:57 no need of gcd,floor,just should hv an idea of coprime no. i.e. they have only d factor 1 in common
	the_phoenixx: 2017-06-28 15:13:24 develop the pattern and thats it
	rohit9934: 2017-06-26 20:12:45 waste my time where O(1) solution exists. Problem statement should be changed to "See the test cases and develop solution"