| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P184PROD - ROUND 4D - Phi hàm ver.N |
Qua hàng vạn, hàng triệu mùa thu chu du khắp các miền, Aki đã học hỏi rất nhiều, đủ để trở thành một giảng viên môn Lý thuyết số tại một trường đại học.
Hôm nay, như thường lệ, lại là một ngày lên lớp của Aki. Bài giảng của anh hôm nay là về phi hàm Euler.
Trong lý thuyết số, phi hàm Euler của một số nguyên dương N - ϕ(N) - được định nghĩa là số lượng các số nguyên tố cùng nhau với N trong đoạn từ 1 đến N.
Ví dụ: ϕ(2) = 1, vì 1 nguyên tố cùng nhau với 2; ϕ(6) = 2, vì 1 và 5 là 2 số nguyên tố cùng nhau với 6.
Aki muốn bài tập về nhà của mình có khả năng phân loại năng lực sinh viên, vì vậy ngoài những bài cơ bản, anh cần phải suy nghĩ thêm 1 bài có tính chất nâng cao hơn.
Biết được điều này, JM thách thức anh một bài toán. Aki không gặp khó khăn gì để giải bài toán này với khối lượng kiến thức mình đã thu thập, nhưng đồng thời anh cũng thấy bài toán phù hợp những gì mình cần. Mất 4 giờ 44 phút 44.44 giây thuyết phục JM, cuối cùng cô cũng đồng ý để Aki sử dụng bài toán này giao cho sinh viên.
Bài toán của JM như sau: Cho một số N cho trước. Hãy tính ϕ(N!).
Yêu cầu của JM và Aki là bài toán chỉ được giải trong tối đa 1s. Bạn có thể làm được không?
Input
Một số nguyên N duy nhất (1 <= N <= 10^7).
Output
Một số nguyên duy nhất là kết quả của bài toán.
Hiển nhiên, N! có thể rất lớn, kéo theo ϕ(N!) cũng lớn không kém, vậy nên JM chỉ yêu cầu tìm đáp số sau khi chia lấy dư cho 10^9+7.
Example
Test 1:
Input: 2 Output: 1
Test 2:
Input:
3
Output:
2
| Được gửi lên bởi: | adm |
| Ngày: | 2018-03-23 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
