Count of integers
Practice
3.7 (19 votes)
Algorithms
Euler's totient function
Greatest common divisor
Math
Number theory
Sieve
Problem
84% Success 6713 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

You are given a positive integer n, for Q queries, You are required to determine the number of integers k (1≤k≤n) such that gcd(k,n)!=1 and gcd(k,n)!=k.

Input format

  • First line: Integer Q denoting the number of queries
  • Next Q lines: Integer n

Output format

Print Q lines each containing an integer that denotes the answer to that specific query.

Constraints

1≤Q≤105

1≤n≤106

Sample Input
1
10
Sample Output
3
Explanation

For c = {1,3,7,9} gcd(c,10) = 1

For c = {2,5,10} gcd(c,10) = c

gcd(4,10) = 2

gcd(6,10) = 2

gcd(8,10) = 2

So, answer is 3.

Code Editor

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Submissions
Please login to view your submissions
Similar Problems
1.4141
Points:30
59 votes
Tags:
ApprovedEasyMathNumber TheoryOpen
2.Finite or infinite
Points:30
10 votes
Tags:
AlgorithmsMathNumber TheoryNumber theory
3.Hacker Decrypting Messages
Points:30
59 votes
Tags:
ApprovedEasyMathNumber theory
Editorial

Login to unlock the editorial