02/10/2018, 14:12
C11PRIME spoj – Số nguyên tố
Nguồn đề bài: http://vn.spoj.com/problems/C11PRIME/ 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à ...
Nguồn đề bài: http://vn.spoj.com/problems/C11PRIME/
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
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.
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. |
