MMOD29 - CALCULATE POW(2004,X) MOD 29

Xét số nguyên dương X và gọi S là tổng tất cả các ước dương của 2004^X .

Cần tính phần dư của S cho 29. Ví dụ, với X=1, các ước dương của 2004^1 là 1, 2, 3, 4, 6, 12, 167, 334, 501, 668, 1002 và 2004. Do đó S = 4704 và số dư của S chia cho 29 là 6.

Input

Gồm nhiều bộ test, mỗi bộ là một số nguyên X (1 <= X <= 10000000).

Bộ test với X = 0 để kết thúc chương trình và không cần xử lý.


Sample Input
1 
10000 
0
Output

Với mỗi bộ test, in ra một kết quả của số dư S chia cho 29 trên 1 dòng.

Sample Input
6 
10 
Note: làm quen với công thức tính tổng các ước số của 1 số - cách tính a^x mod p, cách tính (a^x-1)/(a-1) mod p

Được gửi lên bởi:~!(*(@*!@^&
Ngày:2009-02-21
Thời gian chạy:0.833s
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
Nguồn bài:Peiking 2004

hide comments
2016-06-15 11:04:14 Lương Ðức Tuấn Ðạt
Tham khảo thuật toán và code tại: http://yeulaptrinh.pw/250/mmod29-spoj/
2015-11-26 10:28:29 xin đừng quên tôi
fermat nhỏ :v
2015-09-04 09:22:53
không cần dùng phi vẫn AC -_-
2014-04-17 13:56:29 zai zai
easy in python =))
2014-04-07 07:47:28 John and the cows


Last edit: 2014-04-26 17:19:44
2014-02-21 06:29:50 [deleted]
Đíu liên quan nhưng thím Anh Hào nguy hiểm quá :))
Ở bài này thì b lớn nhất là 166, d = 29. Quá nhỏ.
Thím nên coi lại phi hàm euler. Công thức đó chỉ đúng khi (b, d) = 1 thôi.
Và đề nghị thím đừng quá nguy hiểm nữa, để cho người khác nguy hiểm với :))
2014-01-01 05:08:52 John and the cows
@Danh Nguyen
anh xem giùm a = 42874 b = 34 d = 12 sao dùng công thức này tính không dc ???
2013-12-31 11:44:32 John and the cows
@Lâm Nguyễn
nhỡ b và d cực lớn thì sao????
2013-08-27 15:04:40 [deleted]
@Danh Nguyen: em nghĩ là tính a/b mod d đâu cần dùng tới phi hả anh.
a/b mod d = (a mod (b x d)) / d rồi :D
2013-08-26 10:38:52 [deleted]
mình phục mình quá, quên đọc input :))
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.