Azerbaijan Programming Olympiad - 2nd Stage preparation
Теорія чисел
Математики - цікава порода людей. Особливо в галузі теорії чисел. Вони проводять більшу частину свого часу, думаючи про різні властивості чисел. Альберт Мейєр, фахівець з теорії чисел, намагається відкрити для себе цікаву послідовність натуральних чисел. Він вважає, що послідовність i1
, i2
, i3
,... in
, в якій in
дорівнює кількості таких чисел m, що 1 ≤ m ≤ n, НСД(m, n) ≠ 1 та НСД(m, n) ≠ m, є досить цікавою. Через НСД тут позначено "Найбільший Спільний Дільник". Він звернувся до Вас як до досвідченого програміста з проханням обчислити декілька чисел цієї послідовності.
Вхідні дані
Кожний рядок містить одне натуральне число n (0 < n < 231
).
Вихідні дані
Для кожного значення n вивести в окремому рядку таку кількість чисел m, що 1 ≤ m ≤ n, НСД(m,n)** ≠ 1 та НСД(m,n) ≠ m.
1 2 6 2147000000
0 0 1 1340599805