| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
ETF - Euler Totient Function |
| English | Vietnamese |
In number theory, the totient φ of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n.
Given an integer n (1 <= n <= 10^6). Compute the value of the totient φ.
Input
First line contains an integer T, the number of test cases. (T <= 20000)
T following lines, each contains an integer n.
Output
T lines, one for the result of each test case.
Example
Input: 5 1 2 3 4 5 Output: 1 1 2 2 4
| Được gửi lên bởi: | Race with time |
| Ngày: | 2009-03-27 |
| 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: | Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET |
hide comments
|
||||||
|
2017-08-03 17:57:07
Tham khảo : http://cowboycoder.tech/spoj/spoj-etf |
||||||
|
2017-07-28 18:13:43
Quỳnh |
||||||
|
2016-09-15 03:51:41
mảng hằng =)) |
||||||
|
2016-08-27 08:19:51 Sue
vẫn dùng sàng nguyên tố nhé, nhưng không chạy sàng đến 1e6 mà chỉ chạy đến 1e3 thôi =)) mất vài đấm TLE vì nộp code phi hàm Euler nguyên thủy =)) phải cải tiến 1 tí mới AC :v |
||||||
|
2016-05-15 15:05:23
Chỉ vì Longlong, quái thật... |
||||||
|
2015-08-27 14:00:42
https://traitaodo.wordpress.com/2015/08/27/euler-totient-function-etf/ |
||||||
|
2015-08-10 16:10:27 [Nghien] Le Long
ra google search đúng tên đề bài Euler Totient Function là có solution nhé Last edit: 2015-08-10 16:10:59 |
||||||
|
2015-07-15 17:18:41
=)) Dễ, dễ TLE thì có! |
||||||
|
2015-07-11 19:23:19 Hacking to the Gate
phi(n) = n(1 - 1/p_1)(1 - 1/p_2)...(1 - 1/p_k) (p[1..k] là tập các thừa số nguyên tố phân biệt của n) |
||||||
|
2015-01-12 07:38:37 Phạm Vãn Sơn
Hehe sàng nguyên tố cũng vẫn Limited Time thôi :D ... Có cách khác chỉ 15 line code là AC luôn ^.^ |
||||||
RSS