mình có một vài bài lý thuyết số muốn chia sẻ với mọi người. Nếu ac nào có thêm các bài về lý thuyết số thì cho mình tham khảo với nha! Xin cám ơn.
bài 1. Tìm chữ số cuối cùng khác 0 của n! với n nằm trong khoảng 1..100
Dữ liệu vào cho trong file GT.INP gồm một dòng duy nhất chứa số n
Kết quả ghi ra file GT.OUT gồm một số tương ứng là số khác 0 của n!
Ví dụ :
GT.INP
GT.OUT
7
4
Thuật toán:
-Ý tưởng chính của bài nằm trong công thức 2*5=10
Các chữ cuối cùng bằng 0 của N! được sinh ra khi và chỉ khi trong khai triển ra thừa số nguyên tố của tích trên có chứa các cặp thừa số 2 và 5. Vậy thì trước hết ta đếm số lượng các thừa số 2, kí hiệu là d2 và số lượng các thừa số 5 là d5
Ví dụ : với n=15 ta có dạng khai triển ra thừa số nguyên tố như sau :
15!=1.2.3.(2.2).5.(2.3).7.(2.2.2).(3.3).(2.5).11.(2.2.3).13.(2.7).(3.5)
Do đó d2=11 và d5=3. Vậy ta có 3 căp 2.5=10 và số mũ doi ra của thừa số 2 so với thừa số 5 là d2-d5=11-3=8. Khi đó kết sẽ là : chữ số cuối cùng khác 0 của 15! Bằng chữ số cuối cùng của k.2d2-d5. Trong đó k là tích của các thừa số còn lại.
Việc còn lại là lấy tích k của các số còn lại. Vì tích này không bao giờ tận cùng bằng 0 cho nên ta chỉ cần giữ lại một chữ số cuối cùng bằng cách lấy mod 10
Để tính chữ số tận cùng của 2m với m=d2-d5 >0, ta để ý đến tính tuần hoàn của nó , cụ thể là ta chỉ cần tính chữ số tận cùng của 2 (m mod 4) với các trường hợp m mod 4 bằng 0,1,2,3
Theo ví dụ trên ta có m mod 4=0, do đó chữ số cuối của 2m là 6 chứ không phải là 1 vì m >0. Ta tính được những cặp 2 và 5 được gạch dưới )
15!=1.2.3.4.5.6.7.8.9.10.11.12.13.14.15
= 1.2.3.(2.2).5.(2.3).7.(2.2.2).(3.3).(2.5).11.(2.2.3).13.(2.7).(3.5)
Þ(3.3.7.9.11.13.7.3) 28 mod 10=((k mod 10).(28 mod 10)) mod 10= (3.6) mod 10=8. Chữ số cuối cùng của 15! là 8
Chú ý : (a.b) mod m=((a mod m). (b mod m) mod m cho nên ta có thể lấy mod ở các bước trung gian với số lần tùy ý
Kỹ thuật gán trước : Trong việc tính chữ số tận cùng của 2m bằng các thao tác sau :
Const luythua=array[0..3] of word=(6,2,4,8)
Ý nghĩa của dòng lệnh trên :
khai báo luythua[0]=6 ( =24 mod 10)
luythua[1]=2 ( =21 mod 10)
luythua[0]=4 ( =22 mod 10)
luythua[0]=8 ( =23 mod 10)
Do đó c:=luythua[m mod 4]
const fi='tancung.inp';
fo='tancung.out';
max=1000000;
lt:array[0..3] of integer=(6,2,4,8);
//--------------------------------------------------------------
var n: longint;
//--------------------------------------------------------------
procedure doc;
begin
readln(n);
end;
//--------------------------------------------------------------
procedure xuli;
var i, j: int64;
m, k, kq: longint;
begin
if n<1 then
begin
writeln(1);
exit;
end;
m:=0;
k:=1;
i:=1;
while i<=n do
begin
j:=i;
while j mod 2=0 do
begin
inc(m);
j:=j div 2;
end;
while j mod 5=0 do
begin
dec(m);
j:=j div 5;
end;
k:=(k*(j mod 10)) mod 10;
inc(i);
end;
kq:=(k*lt[m mod 4]) mod 10;
writeln(kq);
end;
//--------------------------------------------------------------
BEGIN
assign(input,fi);
reset(input);
assign(output,fo);
rewrite(output);
doc;
xuli;
close(input);
close(output);
END.
bài 2
Số phong phú (PHONGPHU.PAS)
Trong số học, số phong phú là các số mà tổng các ước số của số đó (không kể chính nó) lớn hơn số đó. Ví dụ, số 12 có tổng các ước số (không kể 12) là 1 + 2 + 3 + 4 + 6 = 16 > 12. Do đó 12 là một số phong phú.
Bạn hãy lập trình đếm xem có bao nhiêu số phong phú trong đoạn [L,R].
Dữ liệu
Gồm 2 số L, R (1 <= L <= R <= 105)
Kết quả
Gồm 1 số nguyên duy nhất là số số phong phú trong đoạn [L, R].
Chú ý
Có 50% số test có 1 <= L <= R <= 103
Ví dụ
NKABD.INP
NKABD.OUT
1 50
9
Từ 1 đến 50 có 9 số phong phú là:
12, 18, 20, 24, 30, 36, 40, 42, 48
code
const fi='phongphu.inp';
fo='phongphu.out';
//-----------------------------------------------
var l, r: longint;
//-----------------------------------------------
procedure doc;
begin
readln(l,r);
end;
//-----------------------------------------------
function tinh(x: longint): longint;
var s, i: longint;
begin
s:=1;
for i:=2 to trunc(sqrt(x)) do
if x mod i=0 then
if (x div i<>i) then s:=s+i+(x div i)
else s:=s+i;
exit(s);
end;
//-----------------------------------------------
procedure xuli;
var i, dem: longint;
begin
dem:=0;
for i:=l to r do
if tinh(i)>i then inc(dem);
writeln(dem);
end;
//-----------------------------------------------
BEGIN
assign(input,fi);
reset(input);
assign(output,fo);
rewrite(output);
doc;
xuli;
close(input);
close(output);
END.
bài 3
Số đẹp
Một số nguyên dương được gọi là đẹp nếu tổng bình phương các chữ số của nó (trong dạng biểu diễn thập phân) là một số nguyên tố.
Ví dụ: 12 là một số đẹp vì 12 + 22 = 5 là số nguyên tố.
Các số đẹp được đánh số theo thứ tự tăng dần của giá trị, bắt đầu từ 1.
Yêu cầu: cho số nguyên N (1<=N<=106). Hãy tìm số đẹp thứ N.
Dữ liệu vào từ tệp văn bản SODEP.INP gồm nhiều dòng, mỗi dòng là một bộ kiểm thử chứa một số nguyên N.
Kết quả ghi ra tệp văn bản SODEP.OUT kết quả của mỗi bộ kiểm thử, mỗi bộ được ghi trên một dòng.
Ví dụ:
SODEP.INP
1
6
SODEP.OUT
11
23
code
const fi='sodep.inp';
fo='sodep.out';
max=1000000;
//-----------------------------------------------
var a: array[1..max] of longint;
n: longint;
//-----------------------------------------------
function kt(n: longint): boolean;
var i, k: longint;
begin
if (n=2) or (n=3) then exit(true);
if (n<2) or (n mod 2=0) or (n mod 3=0) then exit(false);
k:=5;
while k<=trunc(sqrt(n)) do
begin
if (n mod k=0) or (n mod (k+2)=0) then exit(false);
inc(k,6);
end;
exit(true);
end;
//-----------------------------------------------
function tong(n: longint): longint;
var i, s: longint;
st: string;
begin
s:=0;
str(n,st);
for i:=1 to length(st) do s:=s+sqr(ord(st[i])-48);
exit(s);
end;
//-----------------------------------------------
procedure xuli;
var i, dem: longint;
begin
dem:=0;
for i:=2 to max do
if kt(tong(i)) then
begin
inc(dem);
a[dem]:=i;
end;
while not eof do
begin
readln(n);
writeln(a[n]);
end;
end;
//-----------------------------------------------
BEGIN
assign(input,fi);
reset(input);
assign(output,fo);
rewrite(output);
xuli;
close(input);
close(output);
END.