提交记录 19299


用户 题目 状态 得分 用时 内存 语言 代码长度
cmtang 1005a. 【模板题】高精度除法 Accepted 100 537.615 ms 92 KB C++17 2.62 KB
提交时间 评测时间
2023-04-03 23:16:59 2023-04-03 23:17:02
#include <bits/stdc++.h>

using namespace std;

constexpr size_t N {10010};

signed char a[N], b[N], c[N];

size_t a_len;
size_t b_len;

void print_number(signed char *c, size_t len)
{
    for (size_t i {0}; i < len; ++i)
    {
        cout << (signed char)(c[i] + 0x30);
    }
    cout << "\n";
}

bool ge(signed char *a, size_t a_len, signed char *b, size_t b_len)
{
    /*
    if (b_len > 2)
    {
    cout << "ge()\n";
    cout << "a: ";
    print_number(a, a_len);
    cout << "b: ";
    print_number(b, b_len);
    }
    */
    if (a_len < b_len)
        return false;
    if (a_len > b_len)
        return true;
    for (size_t i {0}; i < b_len; ++i)
    {
        if (b[i] > a[i])
            return false;
        else if (a[i] > b[i])
            return true;
    }
    return true;
}

size_t sub(signed char *a, size_t a_len, signed char *b, size_t b_len)
{
    ptrdiff_t a_idx {a_len - 1}, b_idx {b_len - 1};
    while (a_idx >= 0)
    {
        if (a[a_idx] < b[b_idx])
        {
            a[a_idx - 1] -= 1;
            a[a_idx] += 10;
        }
        a[a_idx] -= b[b_idx];
        --a_idx;
        --b_idx;
    }
    size_t z_len {0};
    while (z_len < a_len && a[z_len] == 0)
        ++z_len;
    if (z_len > 0)
    {
        for (size_t i {z_len}; i < a_len; ++i)
        {
            a[i - z_len] = a[i];
            a[i] = 0;
        }
    }
    return a_len - z_len;
}

void divide()
{
    // cout << a_len << " " << b_len << "\n";
    auto m {a_len};
    for (size_t i {0}; i < m; ++i)
    {
        auto div_len {b_len + m - i - 1};

        //cout << "a: ";
        // print_number(a, a_len);
        //cout << "b: ";
        // print_number(b, div_len);
        while (ge(a, a_len, b, div_len))
        {
            /*
            cout << "a: ";
            print_number(a, a_len);
            cout << "b: ";
            print_number(b, div_len);
            */

            c[i] += 1;
            a_len = sub(a, a_len, b, div_len);
            
        }
    }
}

int main() 
{
    /*
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    */

    string s1, s2;
    cin >> s1 >> s2;
    // cout << s1 << " " << s2 << "\n";

    if (s1.length() < s2.length() || (s1.length() == s2.length() && s1 < s2))
    {
        s1.swap(s2);
    }

    a_len = s1.length();
    b_len = s2.length();
    for (size_t i {0}; i < a_len; ++i)
        a[i] = s1[i] - 0x30;
    for (size_t i {0}; i < b_len; ++i)
        b[i] = s2[i] - 0x30;
    auto last {a_len - 1};

    divide();

    size_t i {0};
    while (i < last && c[i] == 0)
    {
        ++i;
    }
    while (i <= last)
    {
        cout << char(c[i] + 0x30);
        ++i;
    }
    cout << "\n";

}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1537.615 ms92 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2024-10-05 12:22:52 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用