Nguồn đề bài: http://vn.spoj.com/problems/C11PRIME/
Nội dung bài viết
1. Đề bài C11PRIME spoj
Số nguyên tố là số chỉ chia hết cho 1 và chính nó. Trong một buổi dã ngoại của trường, bất ngờ TMB bị thầy giáo đố một câu như sau: “Một số có dạng p^q là lũy thừa cao của một số nguyên tố khi và chỉ khi p là một số nguyên tố và q > 1. Thầy sẽ cho em một số N bất kỳ và em hãy cho biết đó có phải là lũy thừa cao của một số nguyên tố hay không?”. Không phải lúc nào cũng mang theo máy tính bên mình, đây là lúc TMB cần bạn.
Yêu cầu: Cho số N, hãy giúp TMB trả lời câu đố của thầy giáo, nếu N là lũy thừa cao của một số nguyên tố thì in ra 2 số p và q tương ứng, nếu không thì ghi 0.
Giới hạn:
n <= 10^18
Input:
1 dòng duy nhất chứa n
Output:
1 dòng duy nhất là kết quả
Ví dụ:
Input | Output |
27 | 3 3 |
Input | Output |
10 | 0 |
2. code tham khảo C11PRIME
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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | const fi=''; vc=high(int64); du=1000000000000000000; type data=longint; data1=int64; var N:data1; f:text; function KTSNT(n:data1):boolean; var i:data; begin for i:=2 to trunc(sqrt(n)) do if n mod i=0 then exit(false); exit(true); end; function tinhcan(a:int64; b:data1):int64; begin tinhcan:=round(exp(ln(a)/b)); end; function amuk(a:int64; k:data):int64; var i:data; res:int64; begin res:=1; for i:=1 to k do begin res:=(res*a) mod du; end; exit(res); end; procedure xuli; var i,j:data; so:data1; begin for i:=2 to 60 do begin so:=tinhcan(n,i); if (amuk(so,i)=n) and ktsnt(so) then begin writeln(so,' ',i); exit; end; end; writeln(0); end; begin assign(f,fi); reset(f); readln(f,n); close(f); xuli; end. |
Bài viết liên quan
- BCMULONE spoj PTIT -Nhân 1
- P134SUMB spoj PTIT – SUM4 B – Lát sàn
- BCTEST14 spoj PTIT – Ốc sên
- COUNTCBG spoj – Phân tích số nguyên
- PTIT124J spoj – chuyển nhị phân sang bát phân
- ANT spoj – Kiến
- MYSTERY spoj – Số huyền bí
- Ước chung lớn nhất, bội chung nhỏ nhất (Cơ bản)
- BCCOM spoj PTIT – Số nén tối giản
- BCACM11A spoj PTIT – Phương án khuyến mãi