#include <stdio.h>
#include <stdint.h>
 
typedef uint64_t u64;
 
// 修改後的除法函數，返回商和餘數
void nvme_u64_div(u64 dividend, u64 divisor, u64* quotient, u64* remainder) {
    *quotient = 0;
    *remainder = 0;
    int i;
    for (i = 63; i >= 0; i--) {
        *remainder = (*remainder << 1) | ((dividend >> i) & 1);
        if (*remainder >= divisor) {
            *remainder -= divisor;
            *quotient |= (1ULL << i);
        }
    }
}
 
// 測試案例結構
typedef struct {
    u64 dividend;
    u64 divisor;
    u64 expected_quotient;
    u64 expected_remainder;
} TestCase;
 
// 執行測試並打印結果
void run_test_case(TestCase test) {
    u64 quotient, remainder;
    nvme_u64_div(test.dividend, test.divisor, &quotient, &remainder);
 
    printf("Dividend: %llu\n", test.dividend);
    printf("Divisor: %llu\n", test.divisor);
    printf("Expected Quotient: %llu\n", test.expected_quotient);
    printf("Actual Quotient: %llu\n", quotient);
    printf("Expected Remainder: %llu\n", test.expected_remainder);
    printf("Actual Remainder: %llu\n", remainder);
    printf("Test %s\n\n", 
           (quotient == test.expected_quotient && remainder == test.expected_remainder) 
           ? "PASSED" : "FAILED");
}
 
int main() {
    // 測試案例數組
    TestCase test_cases[] = {
        // 正常案例
        {1000000000000000000ULL, 3ULL, 333333333333333333ULL, 1ULL},
        {9223372036854775807ULL, 2ULL, 4611686018427387903ULL, 1ULL},
        {18446744073709551615ULL, 9223372036854775807ULL, 2ULL, 1ULL},
 
        // 邊界案例
        {18446744073709551615ULL, 1ULL, 18446744073709551615ULL, 0ULL},
        {18446744073709551615ULL, 18446744073709551615ULL, 1ULL, 0ULL},
        {0ULL, 18446744073709551615ULL, 0ULL, 0ULL},
 
        // 特殊案例
        {18446744073709551614ULL, 2ULL, 9223372036854775807ULL, 0ULL},
        {18446744073709551615ULL, 2ULL, 9223372036854775807ULL, 1ULL},
        {18446744073709551615ULL, 3ULL, 6148914691236517205ULL, 0ULL},
 
        // 質數案例
        {18446744073709551557ULL, 11ULL, 1676976734155413778ULL, 9ULL},
        {18446744073709551557ULL, 18446744073709551557ULL, 1ULL, 0ULL},
 
        // 2的冪次方案例
        {9223372036854775808ULL, 2ULL, 4611686018427387904ULL, 0ULL},
        // 注意：2^64 溢出了 u64，所以我們不包括這個案例
    };
 
    int num_tests = sizeof(test_cases) / sizeof(test_cases[0]);
 
    for (int i = 0; i < num_tests; i++) {
        printf("Test Case %d:\n", i + 1);
        run_test_case(test_cases[i]);
    }
 
    return 0;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRpbnQuaD4KCnR5cGVkZWYgdWludDY0X3QgdTY0OwoKLy8g5L+u5pS55b6M55qE6Zmk5rOV5Ye95pW477yM6L+U5Zue5ZWG5ZKM6aSY5pW4CnZvaWQgbnZtZV91NjRfZGl2KHU2NCBkaXZpZGVuZCwgdTY0IGRpdmlzb3IsIHU2NCogcXVvdGllbnQsIHU2NCogcmVtYWluZGVyKSB7CiAgICAqcXVvdGllbnQgPSAwOwogICAgKnJlbWFpbmRlciA9IDA7CiAgICBpbnQgaTsKICAgIGZvciAoaSA9IDYzOyBpID49IDA7IGktLSkgewogICAgICAgICpyZW1haW5kZXIgPSAoKnJlbWFpbmRlciA8PCAxKSB8ICgoZGl2aWRlbmQgPj4gaSkgJiAxKTsKICAgICAgICBpZiAoKnJlbWFpbmRlciA+PSBkaXZpc29yKSB7CiAgICAgICAgICAgICpyZW1haW5kZXIgLT0gZGl2aXNvcjsKICAgICAgICAgICAgKnF1b3RpZW50IHw9ICgxVUxMIDw8IGkpOwogICAgICAgIH0KICAgIH0KfQoKLy8g5ris6Kmm5qGI5L6L57WQ5qeLCnR5cGVkZWYgc3RydWN0IHsKICAgIHU2NCBkaXZpZGVuZDsKICAgIHU2NCBkaXZpc29yOwogICAgdTY0IGV4cGVjdGVkX3F1b3RpZW50OwogICAgdTY0IGV4cGVjdGVkX3JlbWFpbmRlcjsKfSBUZXN0Q2FzZTsKCi8vIOWft+ihjOa4rOippuS4puaJk+WNsOe1kOaenAp2b2lkIHJ1bl90ZXN0X2Nhc2UoVGVzdENhc2UgdGVzdCkgewogICAgdTY0IHF1b3RpZW50LCByZW1haW5kZXI7CiAgICBudm1lX3U2NF9kaXYodGVzdC5kaXZpZGVuZCwgdGVzdC5kaXZpc29yLCAmcXVvdGllbnQsICZyZW1haW5kZXIpOwogICAgCiAgICBwcmludGYoIkRpdmlkZW5kOiAlbGx1XG4iLCB0ZXN0LmRpdmlkZW5kKTsKICAgIHByaW50ZigiRGl2aXNvcjogJWxsdVxuIiwgdGVzdC5kaXZpc29yKTsKICAgIHByaW50ZigiRXhwZWN0ZWQgUXVvdGllbnQ6ICVsbHVcbiIsIHRlc3QuZXhwZWN0ZWRfcXVvdGllbnQpOwogICAgcHJpbnRmKCJBY3R1YWwgUXVvdGllbnQ6ICVsbHVcbiIsIHF1b3RpZW50KTsKICAgIHByaW50ZigiRXhwZWN0ZWQgUmVtYWluZGVyOiAlbGx1XG4iLCB0ZXN0LmV4cGVjdGVkX3JlbWFpbmRlcik7CiAgICBwcmludGYoIkFjdHVhbCBSZW1haW5kZXI6ICVsbHVcbiIsIHJlbWFpbmRlcik7CiAgICBwcmludGYoIlRlc3QgJXNcblxuIiwgCiAgICAgICAgICAgKHF1b3RpZW50ID09IHRlc3QuZXhwZWN0ZWRfcXVvdGllbnQgJiYgcmVtYWluZGVyID09IHRlc3QuZXhwZWN0ZWRfcmVtYWluZGVyKSAKICAgICAgICAgICA/ICJQQVNTRUQiIDogIkZBSUxFRCIpOwp9CgppbnQgbWFpbigpIHsKICAgIC8vIOa4rOippuahiOS+i+aVuOe1hAogICAgVGVzdENhc2UgdGVzdF9jYXNlc1tdID0gewogICAgICAgIC8vIOato+W4uOahiOS+iwogICAgICAgIHsxMDAwMDAwMDAwMDAwMDAwMDAwVUxMLCAzVUxMLCAzMzMzMzMzMzMzMzMzMzMzMzNVTEwsIDFVTEx9LAogICAgICAgIHs5MjIzMzcyMDM2ODU0Nzc1ODA3VUxMLCAyVUxMLCA0NjExNjg2MDE4NDI3Mzg3OTAzVUxMLCAxVUxMfSwKICAgICAgICB7MTg0NDY3NDQwNzM3MDk1NTE2MTVVTEwsIDkyMjMzNzIwMzY4NTQ3NzU4MDdVTEwsIDJVTEwsIDFVTEx9LAoKICAgICAgICAvLyDpgornlYzmoYjkvosKICAgICAgICB7MTg0NDY3NDQwNzM3MDk1NTE2MTVVTEwsIDFVTEwsIDE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCAwVUxMfSwKICAgICAgICB7MTg0NDY3NDQwNzM3MDk1NTE2MTVVTEwsIDE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCAxVUxMLCAwVUxMfSwKICAgICAgICB7MFVMTCwgMTg0NDY3NDQwNzM3MDk1NTE2MTVVTEwsIDBVTEwsIDBVTEx9LAoKICAgICAgICAvLyDnibnmrormoYjkvosKICAgICAgICB7MTg0NDY3NDQwNzM3MDk1NTE2MTRVTEwsIDJVTEwsIDkyMjMzNzIwMzY4NTQ3NzU4MDdVTEwsIDBVTEx9LAogICAgICAgIHsxODQ0Njc0NDA3MzcwOTU1MTYxNVVMTCwgMlVMTCwgOTIyMzM3MjAzNjg1NDc3NTgwN1VMTCwgMVVMTH0sCiAgICAgICAgezE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCAzVUxMLCA2MTQ4OTE0NjkxMjM2NTE3MjA1VUxMLCAwVUxMfSwKCiAgICAgICAgLy8g6LOq5pW45qGI5L6LCiAgICAgICAgezE4NDQ2NzQ0MDczNzA5NTUxNTU3VUxMLCAxMVVMTCwgMTY3Njk3NjczNDE1NTQxMzc3OFVMTCwgOVVMTH0sCiAgICAgICAgezE4NDQ2NzQ0MDczNzA5NTUxNTU3VUxMLCAxODQ0Njc0NDA3MzcwOTU1MTU1N1VMTCwgMVVMTCwgMFVMTH0sCgogICAgICAgIC8vIDLnmoTlhqrmrKHmlrnmoYjkvosKICAgICAgICB7OTIyMzM3MjAzNjg1NDc3NTgwOFVMTCwgMlVMTCwgNDYxMTY4NjAxODQyNzM4NzkwNFVMTCwgMFVMTH0sCiAgICAgICAgLy8g5rOo5oSP77yaMl42NCDmuqLlh7rkuoYgdTY077yM5omA5Lul5oiR5YCR5LiN5YyF5ous6YCZ5YCL5qGI5L6LCiAgICB9OwoKICAgIGludCBudW1fdGVzdHMgPSBzaXplb2YodGVzdF9jYXNlcykgLyBzaXplb2YodGVzdF9jYXNlc1swXSk7CgogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBudW1fdGVzdHM7IGkrKykgewogICAgICAgIHByaW50ZigiVGVzdCBDYXNlICVkOlxuIiwgaSArIDEpOwogICAgICAgIHJ1bl90ZXN0X2Nhc2UodGVzdF9jYXNlc1tpXSk7CiAgICB9CgogICAgcmV0dXJuIDA7Cn0K