CALCULATE POW(2004,X) MOD 29

View as PDF

Submit solution


Points: 0.28 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Peiking 2004
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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~ ~\left(1 \leq X \leq 10000000\right)~.

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

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

1 
10000 
0

Sample Output

6
10

Comments

Please read the guidelines before commenting.



  • 5
    PPAP_1264589   commented on Aug. 22, 2021, 10:48 p.m. edited

    Việc nhân kết quả với

    pow(2^27)*pow(166^27) % 29

    thực ra cũng chính là

    nhân với 9 rồi %29