Thương và dư - LCOJ: Luyện Code Online Judge

DIVMOD - Thương và dư

Điểm: 1,00 (OI)

Giới hạn thời gian: 0.005s

Giới hạn bộ nhớ: 256M

Tác giả:

siro

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Cho biểu thức ~n = p × k + r~, ~(0 \le r < k)~
Yêu cầu: Tìm giá trị của ~p~ và ~r~ khi biết ~n~ và ~k~.

Input

Hai số nguyên dương ~n~ và ~k (1 \le n, k \le 10^{100})~

Output

In ra hai số nguyên dương ~p~ và ~r~ cần tìm.

Sample

Input #1

5 2

Output #1

2 1

Hint

Giải thích #1: ~2 × 2 + 1 = 5~

Bình luận

Please read the guidelines before commenting.

include <iostream>

include <string>

include <algorithm>

using namespace std;

// Hàm so sánh hai chuỗi số lớn bool isSmaller(const string& str1, const string& str2) { if (str1.length() < str2.length()) return true; if (str1.length() > str2.length()) return false; return str1 < str2; }

// Hàm trừ hai số lớn (str1 >= str2) string subtractBigInt(string str1, string str2) { string res = ""; int n1 = str1.length(), n2 = str2.length(); reverse(str1.begin(), str1.end()); reverse(str2.begin(), str2.end());

int borrow = 0;
for (int i = 0; i < n2; i++) {
    int sub = ((str1[i] - '0') - (str2[i] - '0') - borrow);
    if (sub < 0) {
        sub += 10;
        borrow = 1;
    } else {
        borrow = 0;
    }
    res.push_back(sub + '0');
}
for (int i = n2; i < n1; i++) {
    int sub = ((str1[i] - '0') - borrow);
    if (sub < 0) {
        sub += 10;
        borrow = 1;
    } else {
        borrow = 0;
    }
    res.push_back(sub + '0');
}
while (res.length() > 1 && res.back() == '0') res.pop_back();
reverse(res.begin(), res.end());
return res;

}

int main() { // Tối ưu hóa tốc độ I/O để đạt 0.001s iosbase::syncwith_stdio(false); cin.tie(NULL);

string n, k;
if (!(cin >> n >> k)) return 0;

if (isSmaller(n, k)) {
    cout << "0 " << n << "\n";
    return 0;
}

string quotient = "";
string remainder = "";

for (char c : n) {
    remainder.push_back(c);
    if (remainder.length() > 1 && remainder[0] == '0') {
        remainder.erase(0, 1);
    }

    int count = 0;
    while (!isSmaller(remainder, k)) {
        remainder = subtractBigInt(remainder, k);
        count++;
    }
    quotient.push_back(count + '0');
}

// Xóa các số 0 vô nghĩa ở đầu thương số
while (quotient.length() > 1 && quotient[0] == '0') {
    quotient.erase(0, 1);
}

cout << quotient << " " << remainder << "\n";
return 0;

}

0

Maigv_2010 đã bình luận lúc 15, Tháng 5, 2026, 10:03

TLE?

1

haidang3004 đã bình luận lúc 16, Tháng 12, 2023, 15:45

admin tăng thời gian đi ạ

1

TraiDatHinhAmTra đã bình luận lúc 16, Tháng 12, 2023, 11:26

someone help me please