Azerbaijan Programming Olympiad - 2nd Stage preparation
Mathematicians are a curious breed of people. Especially number theorists. They spend most of their time thinking about different properties of numbers. Albert Meyer, a number theorist, is trying to discover an interesting sequence of positive integers. He suspects the sequence
in which the value of
in is the number of numbers m, such that 1 ≤ m ≤ n, gcd(m, n) ≠ 1 and gcd(m, n) ≠ m, is very interesting. gcd is short for "greatest common divisor". He has turned to you, as you are an expert programmer and the calculations by hand are very tedious, to calculate a few numbers in this sequence.
Each line contains one positive integer n (0 < n <
For each number n print the amount of numbers m, such that 1 ≤ m ≤ n, gcd(m, n) ≠ 1 and gcd(m, n) ≠ m.
1 2 6 2147000000
0 0 1 1340599805