| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P155SUMJ - ROUND 5J - Phi hàm Euler |
Tí đang học về phi hàm Euler. Phi hàm Euler của số n (phi(n)) được định nghĩa bằng số các số nhỏ hơn n và nguyên tố cùng nhau với n. Thấy mọi thứ có vẻ dễ dàng đối với Tí, cô giáo quyết định ra một bài tập khó hơn như sau:
Với số nguyên n, mỗi bước nhảy được tính bằng phép thế n = phi(n). Hỏi sau bao nhiêu bước nhảy, n sẽ bằng 1?
Tí loay hoay một hồi chưa nghĩ ra cách giải quyết. Các bạn hãy giúp Tí nhé!
Input
Dòng đầu tiên là gồm 2 số lượng bộ test T (T <= 100 000).
T dòng tiếp theo, mỗi dòng gồm 8 số nguyên a, b, c, d, e, f, g, h (<= 2 000 000), biểu diễn số n bằng n = abcdefgh.
Output
Với mỗi test, in ra số bước nhảy trên một dòng.
Example
Input:2
2 2 2 1 3 1 6 1
2 1 3 1 5 1 11 1
Output:6
7
Giải thích test 1: n = 22.2.3.6 = 144. Chuỗi bước nhảy như sau:
144 -> 48 ->16 -> 8 -> 4 ->2 -> 1
| Được gửi lên bởi: | adm |
| Ngày: | 2015-07-31 |
| 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 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
