Sáng kiến kinh nghiệm Vận dụng kiến thức số học trong việc lập trình giải các bài toán bằng ngôn ngữ C++

Chương trình:
#include 
using namespace std;
int main()
{ freopen ("chiahet.inp","r",stdin);
freopen("chiahet.out","w",stdout);
long long s,n;
cin>>n;
8.	s=n-n/2-n/3-n/7-n/5+n/6+n/14+n/10+n/21+n/35+n/15- n/42-n/70-n/30-n/105+n/210;
cout<<s;
return 0;
11. }
Bài 11.
Cho hai số nguyên dương a và b, bạn hãy tính S(a,b) = a3 + (a+1)3 +  + b3.
Input: Từ file BEGIN19.INP gồm:
Dòng đầu chứa số nguyên dương T – số testcase
Input
Output
2
36
1 3
405
4 6


	T dòng tiếp mỗi dòng là một cặp số nguyên dương (a, b). Output: Gồm T dòng, mỗi dòng in ra S(a,b) tương ứng. Ví dụ:
40% số test có a ≤ b ≤ 100 và T ≤ 1000
60% số test còn lại có a ≤ b ≤ 104 và T ≤ 106
Thuật toán:
Với a ≤ b ≤ 100 và T ≤ 1000. Ta sẽ duyệt một biến i từ a đến b rồi tăng thêm kết quả một giá trị i3. Đpt bài toán là O((b – a).T).
Với a ≤ b ≤ 104 và T ≤ 106. Ta có thể đưa ra công thức tính
F[N] = 13 + 23 +  + N3 = 𝑁2.(𝑁+1)2 (chứng minh bằng phương pháp quy nạp)
4
Do đó kết quả sẽ là F[b] – F[a – 1], mỗi cặp (a, b) ta sẽ đưa ra kết quả với tốc độ O(1), do đó đpt bài toán sẽ là O(T).
Chương trình:
#include	
using	namespace	std;
long long a,b,c;
long long pw(long long A,long long B,long long C) 5. {
if (B==0) return 1;
long long tmp=pw(A,B/2,C);
tmp=(tmp*tmp)%C;
9. if (B%2==1) tmp=(tmp*A)%C;
10. return tmp;
11. }
12. int main()
13. {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
16. cin>>a>>b>>c;
17. cout<<pw(a,b,c)<<'\n';
18. return 0;
19. }
Bài 12.
Cho một số nguyên dương K, hãy tìm N nhỏ nhất sao cho (N!) có ít nhất K chữ số 0 tận cùng.
Input: Từ file BEGIN20.INP gồm một dòng duy nhất chứa số nguyên dương
K.
Kết quả: Trong file BEGIN20.OUT in ra N thỏa mãn yêu cầu đề bài.
Ví dụ:
Input
Output
3
15
10% số test có K ≤ 4
50% số test khác có K ≤ 105
40% số test còn lại có K ≤ 1015
Thuật toán:
Với K ≤ 4. Ta sẽ thử lần lượt mọi giá trị N từ 1, nhận thấy N sẽ không vượt quá 20 nên ta cứ duyệt rồi với mỗi giá trị N ta lại tính (N!) để đối chiếu.
Với K ≤ 105. Nhận thấy rằng việc có ít nhất K chữ số 0 tận cùng chính là việc chia hết cho 10K, ở trong (N!) thì số TSNT 2 sẽ xuất hiện nhiều hơn số TSNT 5, do đó cho nên ta chỉ cần để ý xem (N!) có chia hết cho 5K hay không. Ta sẽ cho một biến i xuất phát từ 1, rồi cứ tăng i lên, với mỗi i ta lại cộng vào biết kết quả số TSNT 5 mà i chứa, rồi cho đến lúc kết quả lớn hơn hoặc bằng K thì break. Nhận thấy rằng i sẽ không chạy quá 106. Đpt bài toán có thể được đánh giá xấp xỉ O(5K).
Với K ≤ 1015. Dễ thấy, với N càng lớn thì sẽ càng chứa nhiều TSNT 5, do đó ở đây ta sẽ chặt nhị phân N, với mỗi N ta tính xem trong N có bao nhiêu TSNT 5, sẽ chỉ mất O(log(N)) cho điều này. Nếu số TSNT 5 trong N mà lớn hơn hoặc bằng K thì lưu kết quả và giảm N xuống, nếu không tăng N lên. ĐPT cho bài toán này là O(log(1015)2).
Chương trình:
#include	
#define LL long long
using	namespace	std;
LL K,dau,cuoi,mid,ans;
LL cal(LL X,LL P){
LL sum=0;
while (X>0){
sum+=(X/P);
X/=P; 8. }
9. return sum;
10. }
int	main(){
cin>>K;
dau=1;cuoi=1e16;
while (dau<=cuoi){
mid=(dau+cuoi)>>1;
if (cal(mid,5)>=K){
ans=mid;
cuoi=mid-1;
19.	}
20.	else dau=mid+1;
21. }
cout<<ans;
return 0;
24. }
Bài 13.
Nam có gửi đơn xin việc tại một công ty công nghệ thông tin. Người phỏng vấn yêu cầu Nam lập trình để giải quyết một bài toán đơn giản: “ Đưa ra hai chữ số tận cùng của 5n”. Nam đã vượt qua cuộc phỏng vấn một cách dễ dàng, nhưng 24 người trước đó được phỏng vấn, đều thất bại trong câu hỏi này. Vậy Nam đã lập trình giải quyết bài toán này như thế nào?
Input: Một số nguyên n duy nhất (2≤n≤2∙1018)
Output: Hai chữ số tận cùng của 5n.
Ví dụ:
Input
Ouput
2
25
Thuật toán:
Sử dụng lý thuyết đồng dư và cách tìm chữ số tận cùng của một số. Cụ thể: Bằng cách dùng vòng lặp for để tính T= 5n, sau đó lấy phần dư cho phép chia
T cho 100. Tuy nhiên với cách giải này chưa tối ưu bởi lẽ máy tính thông thường có thể tính được khoảng 106 phép tính trên một giây. Do vậy, với số N lớn lên tới 1018, sẽ vượt quá thời gian giới hạn là 1 giây. Khi đó, việc áp dụng kiến thức về số học đồng dư trở nên cần thiết.
Trong lý thuyết số của Toán học: (A * B) mod C = ((A mod C) * B) mod C Do đó:
5n mod 100 = ((5n-1 mod100).5) mod100
Nhận thấy rằng: 52 = 25
Do đó:
53 mod100 = ((52 mod100).5) mod100 = (25.5) mod100 = 25
54 mod100 = ((53 mod100).5) mod100 = (25.5) mod100 = 25
..
5n mod100 = ((5n-1 mod100).5) mod100 = (25.5) mod100 = 25
Do vậy, bài toán này đơn giản đưa ra hai chữ số tận cùng của 5n chính là 25
Chương trình:
#include 
using namespace std;
int main()
4. { cout << "25" << endl;
5. return 0; 6. }
Bài 14.
Cho một xâu s gồm các chữ số. Nhiệm vụ của bạn là tìm những xâu con mà chia hết cho 4. Một xâu con có thể bắt đầu bằng 0. Một xâu con của một xâu là một dãy không rỗng các kí tự liên tiếp nhau trong xâu s. Cho ví dụ, nếu xâu s là 124 thì ta sẽ có 4 xâu chia hết cho 4 là 12,4,24, và 124. Với xâu 04 thì câu trả lời là 3: 0,4,04.
Input:
Chứa xâu s (độ dài của xâu s từ 1 tới 3*105). Xâu s chỉ chứa những con số thuộc khoảng [0,9]
Output:
Đưa ra số nguyên a, số những xâu con của xâu s mà chia hết cho 4
Ví dụ:
Input
Output
124
4
04
3
5810438174
9
Thuật toán:
Sử dụng tính chất chia hết cho 4. Một số chia hết cho 4 khi chính số đó chia hết cho 4, hoặc hai chữ số tận cùng của số đó chia hết cho 4. Từ đó, ta chỉ cần dùng một vòng lặp for để kiểm tra hai chữ số một trong xâu có chia hết cho 4 hay không. Bài toán này nhiều học sinh còn quên mất kiểm tra chính chữ số đó chia hết cho 4.
Chương trình:
#include 
using namespace std;
string s;
int main(){
cin>>s;
int n=s.length();
long long ans=0;
for (int i=0;i<n;i++)
9.	if ((s[i]-'0')%4==0) ans++;
10.	for (int i=1;i<n;i++)
11.	if (((s[i-1]-'0')*10+(s[i]-'0'))%4==0) ans+=i;
cout<<ans;
return 0;
14. }
Bài 15.
Nam rất thích số 30. Một lần nọ, Nam nhìn thấy một số nguyên dương N. Anh muốn hoán đổi các chữ số của N để thu được một bội số lớn nhất của 30. Hãy viết một chương trình giúp Nam thực hiện điều đó
Input
Output
30
30
102
210

Input: Số nguyên dương N, với N có tối đa 105 chữ số Output: Đưa ra bội số cần tìm. Nếu không tìm thấy, đưa ra -1 Ví dụ:
Thuật toán:
Sử dụng dấu hiệu chia hết cho các số 2,3,5. Cụ thể:
Phân tích số 30 ra thừa số nguyên tố là 2*3*5. Do đó, N chia hết cho 30 khi và chỉ khi N chia hết cho 2, 3 và 5. Một số chia hết cho 2 nếu chữ số cuối cùng của số đó là số chẵn, một số chia hết cho 3 nếu tổng các chữ số của số đó chia hết cho 3 và một số chia hết cho 5 nếu chữ số cuối cùng của nó là 0 hoặc 5. Với việc kết hợp các điều kiện trên, ta thấy rằng N chia hết cho 30 nếu và chỉ nếu nó có chữ số tận cùng là 0 và tổng các chữ số của số đó chia hết cho 3. Do đó, nếu Input mà số đó không có chữ số 0 hoặc tổng các chữ số của số đó không chia hết cho 3, ta sẽ đưa ra -1
Giả sử tìm được một số có chữ số tận cùng là 0 và tổng các chữ số chia hết cho
Mà số này phải là số lớn nhất trong các bội số của 30. Do vậy, các chữ số của số này sẽ được sắp xếp theo thứ tự giảm dần để thu được số cần tìm
Độ phức tạp của thuật toán là O(n’logn), trong đó n’ là số lượng các chữ số của
N.
Chương trình:
#include 
using namespace std;
string s;
bool kt = false;
int sum=0;
int soluong[10];
int main(){
cin>>s;
int len=s.length();
for (int i = 0; i<len; ++i) { 11.	sum += s[i] - '0';
12.	kt = kt || s[i] == '0';
13.	++soluong[s[i] - '0'];
14.	}
15.
16.	if (!kt || sum % 3 != 0) { 17.	cout<<"-1";
18.	} else {
19.	for (int i = 9; i >= 0; --i) {
20.	for (int j = 0; j < soluong[i]; ++j) cout<<i;
21.	}
22.	}
23.	return 0;
24. }
Bài 16.
Lan rất thích sưu tầm sách. Các cuốn sách cô mua được đánh số từ 1 tới n. Lan muốn biết có tất cả bao nhiêu chữ số cô vừa viết. Bạn hãy lập trình giúp Lan nhé
Input: Gồm một số nguyên n (1 £ n £ 109 ), số cuốn sách Lan đã đánh số
Output: Đưa ra số lượng các chữ số cần dùng để đánh số tất cả các cuốn sách của Lan
Ví dụ:
Input
Ouput
13
17
4
4

Giải	thích:	Test	đầu	tiên,	các	cuốn	sách	được	đánh	số	là 1,2,3,4,5,6,7,8,9,10,11,12,13, có tất cả 17 chữ số
Thuật toán:
Với n<10, số lượng các chữ số là: n=n-1+1=1*(n+1)-1 số
Với n<100, số lượng các chữ số là: 2*(n-9)+9=2*n-9=2*n-10-1+2=2*(n+1)-11 Với n<1000, số lượng các chữ số là
3*(n-99)+2*(99-9)+9=3*n-99-9=3*n-100-10-1+3=3*(n+1)-111
sz-1
Vì vậy với n<10sz , câu trả lời là
sz *(n +1) - å10i
i=0
trong đó sz là số lượng các
chữ số của n. Độ phức tạp của thuật toán là O(sz), trong đó sz là số lượng các chữ số của n.
Chương trình:
#include 
using namespace std;
int main(){
long long n,d=0;
cin>>n;
for(long long i=1;i<=n;i*=10)d+=n-i+1; 7. cout<<d<<'\n';
Bài 17.
Cho một bảng gồm n hàng và n cột. Các ô ở dòng thứ i và cột thứ j sẽ là số ixj. Dòng và cột được đánh số bắt đầu từ 1. Cho một số nguyên dương x. Nhiệm vụ của bạn là đếm số lượng ô trong bảng chứa số x.
Input: Chứa hai số nguyên n và x(1 £ n £ 105
Input
Output
10 5
2
6 12
4
5 13
0

bảng và số nguyên ta cần tìm trong bảng Output: Số lần x xuất hiện trong bảng Ví dụ:
, 1 £ x £ 109
), kích thước của
Giải thích: Bảng trong ví dụ thứ hai được cho dưới đây. Số 12 được bôi đen
1
2
3
4
5
6
2
4
6
8
10
12
3
6
9
12
15
18
4
8
12
16
20
24
5
10
15
20
25
30
6
12
18
24
30
36
Thuật toán:
Số x xuất hiện trong cột thứ i chỉ một lần, đó là ở dòng x/i. Với mỗi cột i, ta kiểm tra xem x có chia hết cho i và x/i<=n. Nếu tất cả yêu cầu thỏa mãn, ta sẽ cập nhật câu trả lời.
Độ phức tạp của thuật toán là O(n)
Chương trình:
#include 
using namespace std;
int main(){
int i,x,n,a=0;
cin>>n>>x;
6. for(i=1;i<=n;i++)if(x%i==0&&x/i<=n)a++;
cout << a;
return 0; 9. }
Bài 18.
Nam là một người mới bắt đầu lập trình. Hôm nay Nam học về mảng. Cô ấy có một mảng a1,a2,..,an bao gồm n số nguyên dương. Giáo viên của anh cho một nhiệm vụ, tìm số trong mảng thoả mãn tất cả các phần tử của mảng đều chia hết ch