#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);
        }
    }
}
 
// 驗證函數
int verify_result(u64 dividend, u64 divisor, u64 quotient, u64 remainder) {
    return (divisor * quotient + remainder == dividend) && (remainder < divisor);
}
 
// 測試案例結構
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);
    int verification_result = verify_result(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("Verification Result: %s\n", verification_result ? "PASSED" : "FAILED");
    printf("Test %s\n\n", (quotient == test.expected_quotient && remainder == test.expected_remainder && verification_result) ? "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, 1676976733973595596ULL, 1ULL},
        {18446744073709551557ULL, 18446744073709551557ULL, 1ULL, 0ULL},
        // 2的冪次方案例
        {9223372036854775808ULL, 2ULL, 4611686018427387904ULL, 0ULL},
        // 大數除以3^6案例
        {18446744073709551615ULL, 729ULL, 25304175686842458ULL, 603ULL},
        // 其他案例
        {18446744073709551615ULL, 10ULL, 1844674407370955161ULL, 5ULL},
        {18446744073709551615ULL, 9223372036854775806ULL, 2ULL, 3ULL},
        {12345678901234567890ULL, 98765432109876543ULL, 125ULL, 0ULL},
        {18446744073709551615ULL, 18446744073709551610ULL, 1ULL, 5ULL}
    };
 
    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+PSBkaXZpc29yKSB7CiAgICAgICAgICAgICpyZW1haW5kZXIgLT0gZGl2aXNvcjsKICAgICAgICAgICAgKnF1b3RpZW50IHw9ICgxVUxMIDw8IGkpOwogICAgICAgIH0KICAgIH0KfQoKLy8g6amX6K2J5Ye95pW4CmludCB2ZXJpZnlfcmVzdWx0KHU2NCBkaXZpZGVuZCwgdTY0IGRpdmlzb3IsIHU2NCBxdW90aWVudCwgdTY0IHJlbWFpbmRlcikgewogICAgcmV0dXJuIChkaXZpc29yICogcXVvdGllbnQgKyByZW1haW5kZXIgPT0gZGl2aWRlbmQpICYmIChyZW1haW5kZXIgPCBkaXZpc29yKTsKfQoKLy8g5ris6Kmm5qGI5L6L57WQ5qeLCnR5cGVkZWYgc3RydWN0IHsKICAgIHU2NCBkaXZpZGVuZDsKICAgIHU2NCBkaXZpc29yOwogICAgdTY0IGV4cGVjdGVkX3F1b3RpZW50OwogICAgdTY0IGV4cGVjdGVkX3JlbWFpbmRlcjsKfSBUZXN0Q2FzZTsKCi8vIOWft+ihjOa4rOippuS4puaJk+WNsOe1kOaenAp2b2lkIHJ1bl90ZXN0X2Nhc2UoVGVzdENhc2UgdGVzdCkgewogICAgdTY0IHF1b3RpZW50LCByZW1haW5kZXI7CiAgICBudm1lX3U2NF9kaXYodGVzdC5kaXZpZGVuZCwgdGVzdC5kaXZpc29yLCAmcXVvdGllbnQsICZyZW1haW5kZXIpOwogICAgaW50IHZlcmlmaWNhdGlvbl9yZXN1bHQgPSB2ZXJpZnlfcmVzdWx0KHRlc3QuZGl2aWRlbmQsIHRlc3QuZGl2aXNvciwgcXVvdGllbnQsIHJlbWFpbmRlcik7CiAgICAKICAgIHByaW50ZigiRGl2aWRlbmQ6ICVsbHVcbiIsIHRlc3QuZGl2aWRlbmQpOwogICAgcHJpbnRmKCJEaXZpc29yOiAlbGx1XG4iLCB0ZXN0LmRpdmlzb3IpOwogICAgcHJpbnRmKCJFeHBlY3RlZCBRdW90aWVudDogJWxsdVxuIiwgdGVzdC5leHBlY3RlZF9xdW90aWVudCk7CiAgICBwcmludGYoIkFjdHVhbCBRdW90aWVudDogJWxsdVxuIiwgcXVvdGllbnQpOwogICAgcHJpbnRmKCJFeHBlY3RlZCBSZW1haW5kZXI6ICVsbHVcbiIsIHRlc3QuZXhwZWN0ZWRfcmVtYWluZGVyKTsKICAgIHByaW50ZigiQWN0dWFsIFJlbWFpbmRlcjogJWxsdVxuIiwgcmVtYWluZGVyKTsKICAgIHByaW50ZigiVmVyaWZpY2F0aW9uIFJlc3VsdDogJXNcbiIsIHZlcmlmaWNhdGlvbl9yZXN1bHQgPyAiUEFTU0VEIiA6ICJGQUlMRUQiKTsKICAgIHByaW50ZigiVGVzdCAlc1xuXG4iLCAocXVvdGllbnQgPT0gdGVzdC5leHBlY3RlZF9xdW90aWVudCAmJiByZW1haW5kZXIgPT0gdGVzdC5leHBlY3RlZF9yZW1haW5kZXIgJiYgdmVyaWZpY2F0aW9uX3Jlc3VsdCkgPyAiUEFTU0VEIiA6ICJGQUlMRUQiKTsKfQoKaW50IG1haW4oKSB7CiAgICAvLyDmuKzoqabmoYjkvovmlbjntYQKICAgIFRlc3RDYXNlIHRlc3RfY2FzZXNbXSA9IHsKICAgICAgICAvLyDmraPluLjmoYjkvosKICAgICAgICB7MTAwMDAwMDAwMDAwMDAwMDAwMFVMTCwgM1VMTCwgMzMzMzMzMzMzMzMzMzMzMzMzVUxMLCAxVUxMfSwKICAgICAgICB7OTIyMzM3MjAzNjg1NDc3NTgwN1VMTCwgMlVMTCwgNDYxMTY4NjAxODQyNzM4NzkwM1VMTCwgMVVMTH0sCiAgICAgICAgezE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCA5MjIzMzcyMDM2ODU0Nzc1ODA3VUxMLCAyVUxMLCAxVUxMfSwKICAgICAgICAvLyDpgornlYzmoYjkvosKICAgICAgICB7MTg0NDY3NDQwNzM3MDk1NTE2MTVVTEwsIDFVTEwsIDE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCAwVUxMfSwKICAgICAgICB7MTg0NDY3NDQwNzM3MDk1NTE2MTVVTEwsIDE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCAxVUxMLCAwVUxMfSwKICAgICAgICB7MFVMTCwgMTg0NDY3NDQwNzM3MDk1NTE2MTVVTEwsIDBVTEwsIDBVTEx9LAogICAgICAgIC8vIOeJueauiuahiOS+iwogICAgICAgIHsxODQ0Njc0NDA3MzcwOTU1MTYxNFVMTCwgMlVMTCwgOTIyMzM3MjAzNjg1NDc3NTgwN1VMTCwgMFVMTH0sCiAgICAgICAgezE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCAyVUxMLCA5MjIzMzcyMDM2ODU0Nzc1ODA3VUxMLCAxVUxMfSwKICAgICAgICB7MTg0NDY3NDQwNzM3MDk1NTE2MTVVTEwsIDNVTEwsIDYxNDg5MTQ2OTEyMzY1MTcyMDVVTEwsIDBVTEx9LAogICAgICAgIC8vIOizquaVuOahiOS+iwogICAgICAgIHsxODQ0Njc0NDA3MzcwOTU1MTU1N1VMTCwgMTFVTEwsIDE2NzY5NzY3MzM5NzM1OTU1OTZVTEwsIDFVTEx9LAogICAgICAgIHsxODQ0Njc0NDA3MzcwOTU1MTU1N1VMTCwgMTg0NDY3NDQwNzM3MDk1NTE1NTdVTEwsIDFVTEwsIDBVTEx9LAogICAgICAgIC8vIDLnmoTlhqrmrKHmlrnmoYjkvosKICAgICAgICB7OTIyMzM3MjAzNjg1NDc3NTgwOFVMTCwgMlVMTCwgNDYxMTY4NjAxODQyNzM4NzkwNFVMTCwgMFVMTH0sCiAgICAgICAgLy8g5aSn5pW46Zmk5LulM1425qGI5L6LCiAgICAgICAgezE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCA3MjlVTEwsIDI1MzA0MTc1Njg2ODQyNDU4VUxMLCA2MDNVTEx9LAogICAgICAgIC8vIOWFtuS7luahiOS+iwogICAgICAgIHsxODQ0Njc0NDA3MzcwOTU1MTYxNVVMTCwgMTBVTEwsIDE4NDQ2NzQ0MDczNzA5NTUxNjFVTEwsIDVVTEx9LAogICAgICAgIHsxODQ0Njc0NDA3MzcwOTU1MTYxNVVMTCwgOTIyMzM3MjAzNjg1NDc3NTgwNlVMTCwgMlVMTCwgM1VMTH0sCiAgICAgICAgezEyMzQ1Njc4OTAxMjM0NTY3ODkwVUxMLCA5ODc2NTQzMjEwOTg3NjU0M1VMTCwgMTI1VUxMLCAwVUxMfSwKICAgICAgICB7MTg0NDY3NDQwNzM3MDk1NTE2MTVVTEwsIDE4NDQ2NzQ0MDczNzA5NTUxNjEwVUxMLCAxVUxMLCA1VUxMfQogICAgfTsKCiAgICBpbnQgbnVtX3Rlc3RzID0gc2l6ZW9mKHRlc3RfY2FzZXMpIC8gc2l6ZW9mKHRlc3RfY2FzZXNbMF0pOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBudW1fdGVzdHM7IGkrKykgewogICAgICAgIHByaW50ZigiVGVzdCBDYXNlICVkOlxuIiwgaSArIDEpOwogICAgICAgIHJ1bl90ZXN0X2Nhc2UodGVzdF9jYXNlc1tpXSk7CiAgICB9CgogICAgcmV0dXJuIDA7Cn0=