| 1 Оюн Содунам Александрович, 10 сентября 2026 г. 9:31:32 |
| from math import* n = int(input()) a = 0 for i in range(1, n): if (gcd(i, n)) == 1: a += 1 print(a)
|
|
|
| 2 Таранова Елизавета Дмитриевна, 10 сентября 2026 г. 8:39:06 |
| import sys def totient(n: int) -> int: if n <= 1: return 0 nn = n phi = n p = 2 while p * p <= nn: if nn % p == 0: while nn % p == 0: nn //= p phi -= phi // p p += 1 if nn > 1: phi -= phi // nn return phi def main(): data = sys.stdin.read().strip().split() if not data: return n = int(data[0]) print(totient(n)) if __name__ == "__main__": main()
|
|
|
| 3 Абду, 20 января 2026 г. 14:17:37 |
| что там на 6 ом тесте
|
|
|
| 4 Абду, 20 января 2026 г. 14:17:00 |
| какой тест на 6 ом у меня WR
|
|
|
| 5 Ерасыл Данияров, 07 декабря 2025 г. 15:22:50 |
| #include <bits/stdc++.h> using namespace std; // gcd функциясы int gcd(int a, int b) { while(b) { int t = b; b = a % b; a = t; } return a; } int main() { int N; cin >> N; int count = 0; for(int i = 1; i < N; i++) { if(gcd(i, N) == 1) count++; } cout << count << "\n"; return 0; } легко
|
|
|
| 6 Иван Андреевич, 10 апреля 2024 г. 18:58:09 |
Будьте уважні при підрахунку функції Ейлера, може бути переповнення int'а.
Если сначала делить, а потом умножать - то не будет.
|
|
|
| 7 Айтбатыр, 10 января 2023 г. 8:33:36 |
| Шамсиддин, вы правы, НОД 6 и 2 равняется 2-ум. Однако, нужно посчитать количество чисел, меньших N и взаимно простых с ним. В нашем случае, эти числа 1 и 5. НОД (6, 1) = 1 и НОД (6, 5) = 1.
|
|
|
| 8 Шамсиддин, 21 октября 2022 г. 15:43:52 |
| А разве НОД 6 и 2 не равняется 2-ум?
|
|
|
| 9 Тереня Михаил Николаевич, 19 августа 2021 г. 14:43:22 |
| Просто фунция Эйлера
|
|
|
| 10 Сафронов Тимофей Николаевич, 18 июля 2020 г. 18:52:52 |
| from math import gcd
|
|
|
| 11 Жамшидхон Кодиров, 13 мая 2019 г. 13:30:34 |
| n =1 ans = 0
|
|
|
| 12 Потапов Андрей Алексанрович, 04 мая 2018 г. 16:38:50 |
Можно ли использовать import?
Можно. Только версия Питона 3.4.3. Это может иметь значение.
|
|
|
| 13 Завгородний Михаил Сергеевич, 29 марта 2018 г. 9:29:42 |
| Алгоритм евклида - самый лучший алгоритм.
|
|
|
| 14 Чоро уулу Нурдин, 09 января 2018 г. 7:19:39 |
| вообще не понял. как если 6 то результат 2 и если 13 то 12. Может кто нибудь подробнее объяснить
|
|
|
| 15 Четвертый Хокаге, 28 декабря 2016 г. 21:56:12 |
1 Темирбаев Мирас, 10 октября 2016 г. 20:19:38
А еще лучше сразу функцию Эйлера.
-> ссылка на тот же сайт
|
|
|
|
|
| 17 Бабиков Евгений Александрович, 15 апреля 2012 г. 9:02:11 |
| До 100000 и без Эйлера можно обойтись, с НОД-ом сдал.
|
|
|
| 18 Волостнов Алексей Сергеевич, 18 февраля 2012 г. 23:06:00 |
Функция Эйлера!
|
|
|
| 19 Глейх Андрей Артурович, 01 января 2012 г. 19:58:04 |
| если была написана программа НОД то надо всего пару строк к кпрограмме добавить
|
|
|
| 20 Яруллин Рамиль, 07 августа 2011 г. 15:32:08 |
| n -> фи(n), где фи - функция Эйлера)
|
|
|
