GCD Пары
(Время: 5 сек. Память: 256 Мб Сложность: 74%)
Для заданного n вычислите количество таких пар целых чисел 1 ≤ i, j ≤ n, что НОД(i2, j) = НОД(i, j2).
НОД — наибольший общий делитель.
Входные данные
В единственной строке входного файла INPUT.TXT содержится целое число n (1 ≤ n ≤ 2×106).
Выходные данные
В единственную строку выходного файла OUTPUT.TXT выведите ответ на задачу.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 5 | 23 |
2 | 10 | 82 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|