当前位置：首页 > news >正文

题解：洛谷 P2005 A/B Problem II

news 2026/5/11 21:54:32

【题目来源】

洛谷：P2005 A/B Problem II - 洛谷

【题目描述】

给出正整数 \(N\) 和 \(M\)，请你计算 \(\lfloor\frac{N}{M}\rfloor\)（\(\frac{N}{M}\) 的下取整）。

【输入】

两行，两个正整数，\(N\) 和 \(M\)。

【输出】

一行，一个整数，表示 \(\lfloor\frac{N}{M}\rfloor\)。

【输入样例】

1000 
333

【输出样例】

【算法标签】

《洛谷 P2005 A/B Problem II》 #高精度# #二分#

【代码详解】

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 20005;
struct BIG
{int len, num[N];BIG(){// 构造函数：将高精度数字初始化为0memset(num, 0, sizeof(num));len = 1;}void set(int x){// 将int类型数字x转化为高精度数字memset(num, 0, sizeof(num));len = 0;while (x>0){num[++len] = x % 10;x /= 10;}if (len==0) len = 1;  // 特判0的情况}void set(string s){// 将string类型转化为高精度数字memset(num, 0, sizeof(num));len = s.size();for (int i=1; i<=len; i++)num[i] = s[len-i] - '0';}void print(){// 输出高精度数字for (int i=len; i>=1; i--)cout << num[i];cout << endl;}
};
BIG operator*(BIG a, int b)
{BIG c;c.len = a.len;int u = 0;for (int i=1; i<=c.len; i++){int t = a.num[i] * b + u;c.num[i] = t % 10;u = t / 10;}while (u>0){c.num[++c.len] = u % 10;u /= 10;}return c;
}
BIG A, B, C;
string s1, s2;
signed main() {cin >> s1 >> s2;A.set(s1);B.set(s2);int l = 0, r = 1e18;while (l < r) {int mid = (l + r + 1) / 2;  // 注意：向上取整cout << "mid " << mid << endl;C = B * mid;cout << "c " << endl;C.print();// 检查 b*mid 是否 ≤ abool condition = true;if (C.num[0] > A.num[0]) {// b*mid的位数比a多，肯定大于acondition = false;} else if (C.num[0] < A.num[0]) {// b*mid的位数比a少，肯定小于acondition = true;} else {// 位数相同，逐位比较bool less = false, greater = false;for (int i = C.num[0]; i >= 1; i--) {if (C.num[i] < A.num[i]) {less = true;break;} else if (C.num[i] > A.num[i]) {greater = true;break;}}// 如果c == a 或 c < a，条件成立condition = !greater;  // 不大于就是小于等于}if (condition) {l = mid;  // 可以尝试更大的mid} else {r = mid - 1;  // 太大了}}cout << l << endl;return 0;
}

【运行结果】