MYSTERY spoj – Số huyền bí
Nguồn đề bài: http://vn.spoj.com/problems/MYSTERY/ 1. Đề bài MYSTERY spoj Đất nước Văn Lang thời cổ xưa đã có những hiểu biết tân tiến về số học. Tương truyền rằng, vua Hùng Vương thứ 17 cùng các trưởng lão trong triều đình đã phát minh ra các số huyền bí. Các số này giúp chỉ dẫn ...
Nguồn đề bài: http://vn.spoj.com/problems/MYSTERY/
1. Đề bài MYSTERY spoj
Đất nước Văn Lang thời cổ xưa đã có những hiểu biết tân tiến về số học. Tương truyền rằng, vua Hùng Vương thứ 17 cùng các trưởng lão trong triều đình đã phát minh ra các số huyền bí. Các số này giúp chỉ dẫn đường vào kho tàng của đất nước.
Theo các chứng tích khảo cổ, các nhà khoa học kết luận rằng số huyền bí cơ sở a bằng tích của (3d-1) với mọi ước số d > 0 của a.
Bờm thích số học đồng thời cũng rất thích tìm hiểu lịch sử đất nước. Bạn hãy giúp Bờm tính số huyền bí cơ sở a (1 ≤ a ≤ 109). Do kết quả có thể rất lớn, bạn chỉ cần in ra phần dư của số huyền bí cơ sở a khi chia cho 20122007.
Dữ liệu
Gồm một số nguyên a duy nhất.
Kết quả
In ra số nguyên duy nhất là phần dư của số huyền bí cơ sở a khi chia cho 20122007.
Ví dụ
Dữ liệu:
10
Kết qủa
7291779
2. Hướng dẫn MYSTERY spoj
– xây dựng hàm power mod (lũy thừa nhanh).
– trực hiện duyệt trâu các số mà a chia hết cho nó.
3. code tham khảo MYSTERY spoj
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | const fi='; base=20122007; type data=longint; var f:text; A,i:data; res:int64; function powermod(a,b:int64):int64; var t:int64; begin if b=0 then exit(1); if b mod 2 = 0 then begin t:=powermod(a,b div 2); exit((t*t) mod base); end; exit((a*powermod(a,b-1)) mod base); end; begin assign(f,fi); reset(f); readln(f,a); close(f); res:=1; for i:=1 to trunc(sqrt(a)) do if a mod i = 0 then begin res:=(res*(powermod(3,i)-1)) mod base; if ((a div i)<>i) then res:=(res*(powermod(3,a div i)-1)) mod base; end; writeln(res); end. |
