Cho một chuỗi số lớn num và một số lớn khác m; nhiệm vụ là in thương số sử dụng phép chia và phần dư của số lớn sử dụng phép modulus.
Đầu ra nên là: Dư = xxx; Thương = yyy
Giả sử đầu vào num = "14598499948265358486" và m = 487 thì dư là 430 và thương là 29976385930729688.
Ví dụ
Đầu vào: num = "214755974562154868", m = 17 Đầu ra: Dư = 15, Thương = 12632704386009109 Đầu vào: num = "214", m = 5 Đầu ra: Dư = 4, Thương = 42
Phương pháp giải quyết:
- Ban đầu đặt mod = 0
- Bắt đầu từ bên trái, tìm mod bằng: mod = (mod * 10 + chữ_số) % m
- Tìm thương bằng quo[i] = mod/m, trong đó i là vị trí của thương
THUẬT TOÁN
BẮT ĐẦU
Bước 1 → Khai báo long long ll
Bước 2 → Trong hàm void quotientremainder(string num, ll m)
Khai báo vector<int> vec
Gán ll mod = 0
VỒNG LẶP i = 0 đến num.size()-1
Gán digit = num[i] - '0'
Gán mod = mod * 10 + digit
Gán quo = mod / m
Gọi vec.push_back(quo)
Gán mod = mod % m
KẾT THÚC VỒNG LẶP
In giá trị dư là mod
Gán zeroflag = 0
VỒNG LẶP i = 0 đến vec.size()-1
NẾU vec[i] == 0 VÀ zeroflag == 0 THÌ
TIẾP TỤC
KẾT THÚC NẾU
Gán zeroflag = 1
In giá trị vec[i]
KẾT THÚC VỒNG LẶP
TRẢ VỀ
Bước 3 → Trong hàm int main()
Khai báo và gán num = "14598499948265358486"
Khai báo và gán ll m = 487
Gọi hàm quotientremainder(num, m)
DỪNG
Ví dụ mã nguồn
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Hàm tính modulus và thương
void quotientremainder(string num, ll m) {
// Lưu thương của số lớn
vector<int> vec;
ll mod = 0;
// Thực hiện phép chia từng bước
for (int i = 0; i < num.size(); i++) {
int digit = num[i] - '0';
// Cập nhật modulo bằng cách nối chữ số hiện tại
mod = mod * 10 + digit;
// Cập nhật thương
int quo = mod / m;
vec.push_back(quo);
// Cập nhật mod cho lần lặp tiếp theo
mod = mod % m;
}
cout << "\nRemainder: " << mod << "\n";
cout << "Quotient: ";
// Cờ để bỏ qua số 0 ở đầu
bool zeroflag = 0;
for (int i = 0; i < vec.size(); i++) {
if (vec[i] == 0 && zeroflag == 0)
continue;
zeroflag = 1;
cout << vec[i];
}
return;
}
// Khối main
int main() {
string num = "14598499948265358486";
ll m = 487;
quotientremainder(num, m);
return 0;
}
Kết quả đầu ra
Remainder: 430 Quotient: 29976385930729688