#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 {
    int is_valid;
    u64 calc_dividend;
    u64 calc_remainder;
} VerificationResult;
 
VerificationResult verify_result(u64 dividend, u64 divisor, u64 quotient, u64 remainder) {
    VerificationResult result;
    result.calc_dividend = divisor * quotient + remainder;
    result.calc_remainder = dividend % divisor;
    result.is_valid = (result.calc_dividend == dividend) && (remainder < divisor);
    return result;
}
 
// 測試案例結構
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);
    VerificationResult ver_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:\n");
    printf("  Calculated Dividend: %llu\n", ver_result.calc_dividend);
    printf("  Calculated Remainder: %llu\n", ver_result.calc_remainder);
    printf("  Is Valid: %s\n", ver_result.is_valid ? "Yes" : "No");
    printf("Test %s\n\n", (quotient == test.expected_quotient && remainder == test.expected_remainder && ver_result.is_valid) ? "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+PSBkaXZpc29yKSB7CiAgICAgICAgICAgICpyZW1haW5kZXIgLT0gZGl2aXNvcjsKICAgICAgICAgICAgKnF1b3RpZW50IHw9ICgxVUxMIDw8IGkpOwogICAgICAgIH0KICAgIH0KfQoKLy8g5pu05paw5b6M55qE6amX6K2J5Ye95pW477yM6L+U5Zue5YWp5YCL6KiI566X57WQ5p6cCnR5cGVkZWYgc3RydWN0IHsKICAgIGludCBpc192YWxpZDsKICAgIHU2NCBjYWxjX2RpdmlkZW5kOwogICAgdTY0IGNhbGNfcmVtYWluZGVyOwp9IFZlcmlmaWNhdGlvblJlc3VsdDsKClZlcmlmaWNhdGlvblJlc3VsdCB2ZXJpZnlfcmVzdWx0KHU2NCBkaXZpZGVuZCwgdTY0IGRpdmlzb3IsIHU2NCBxdW90aWVudCwgdTY0IHJlbWFpbmRlcikgewogICAgVmVyaWZpY2F0aW9uUmVzdWx0IHJlc3VsdDsKICAgIHJlc3VsdC5jYWxjX2RpdmlkZW5kID0gZGl2aXNvciAqIHF1b3RpZW50ICsgcmVtYWluZGVyOwogICAgcmVzdWx0LmNhbGNfcmVtYWluZGVyID0gZGl2aWRlbmQgJSBkaXZpc29yOwogICAgcmVzdWx0LmlzX3ZhbGlkID0gKHJlc3VsdC5jYWxjX2RpdmlkZW5kID09IGRpdmlkZW5kKSAmJiAocmVtYWluZGVyIDwgZGl2aXNvcik7CiAgICByZXR1cm4gcmVzdWx0Owp9CgovLyDmuKzoqabmoYjkvovntZDmp4sKdHlwZWRlZiBzdHJ1Y3QgewogICAgdTY0IGRpdmlkZW5kOwogICAgdTY0IGRpdmlzb3I7CiAgICB1NjQgZXhwZWN0ZWRfcXVvdGllbnQ7CiAgICB1NjQgZXhwZWN0ZWRfcmVtYWluZGVyOwp9IFRlc3RDYXNlOwoKLy8g5Z+36KGM5ris6Kmm5Lim5omT5Y2w57WQ5p6cCnZvaWQgcnVuX3Rlc3RfY2FzZShUZXN0Q2FzZSB0ZXN0KSB7CiAgICB1NjQgcXVvdGllbnQsIHJlbWFpbmRlcjsKICAgIG52bWVfdTY0X2Rpdih0ZXN0LmRpdmlkZW5kLCB0ZXN0LmRpdmlzb3IsICZxdW90aWVudCwgJnJlbWFpbmRlcik7CiAgICBWZXJpZmljYXRpb25SZXN1bHQgdmVyX3Jlc3VsdCA9IHZlcmlmeV9yZXN1bHQodGVzdC5kaXZpZGVuZCwgdGVzdC5kaXZpc29yLCBxdW90aWVudCwgcmVtYWluZGVyKTsKICAgIAogICAgcHJpbnRmKCJEaXZpZGVuZDogJWxsdVxuIiwgdGVzdC5kaXZpZGVuZCk7CiAgICBwcmludGYoIkRpdmlzb3I6ICVsbHVcbiIsIHRlc3QuZGl2aXNvcik7CiAgICBwcmludGYoIkV4cGVjdGVkIFF1b3RpZW50OiAlbGx1XG4iLCB0ZXN0LmV4cGVjdGVkX3F1b3RpZW50KTsKICAgIHByaW50ZigiQWN0dWFsIFF1b3RpZW50OiAlbGx1XG4iLCBxdW90aWVudCk7CiAgICBwcmludGYoIkV4cGVjdGVkIFJlbWFpbmRlcjogJWxsdVxuIiwgdGVzdC5leHBlY3RlZF9yZW1haW5kZXIpOwogICAgcHJpbnRmKCJBY3R1YWwgUmVtYWluZGVyOiAlbGx1XG4iLCByZW1haW5kZXIpOwogICAgcHJpbnRmKCJWZXJpZmljYXRpb24gUmVzdWx0OlxuIik7CiAgICBwcmludGYoIiAgQ2FsY3VsYXRlZCBEaXZpZGVuZDogJWxsdVxuIiwgdmVyX3Jlc3VsdC5jYWxjX2RpdmlkZW5kKTsKICAgIHByaW50ZigiICBDYWxjdWxhdGVkIFJlbWFpbmRlcjogJWxsdVxuIiwgdmVyX3Jlc3VsdC5jYWxjX3JlbWFpbmRlcik7CiAgICBwcmludGYoIiAgSXMgVmFsaWQ6ICVzXG4iLCB2ZXJfcmVzdWx0LmlzX3ZhbGlkID8gIlllcyIgOiAiTm8iKTsKICAgIHByaW50ZigiVGVzdCAlc1xuXG4iLCAocXVvdGllbnQgPT0gdGVzdC5leHBlY3RlZF9xdW90aWVudCAmJiByZW1haW5kZXIgPT0gdGVzdC5leHBlY3RlZF9yZW1haW5kZXIgJiYgdmVyX3Jlc3VsdC5pc192YWxpZCkgPyAiUEFTU0VEIiA6ICJGQUlMRUQiKTsKfQoKaW50IG1haW4oKSB7CiAgICAvLyDmuKzoqabmoYjkvovmlbjntYQKICAgIFRlc3RDYXNlIHRlc3RfY2FzZXNbXSA9IHsKICAgICAgICAvLyDmraPluLjmoYjkvosKICAgICAgICB7MTAwMDAwMDAwMDAwMDAwMDAwMFVMTCwgM1VMTCwgMzMzMzMzMzMzMzMzMzMzMzMzVUxMLCAxVUxMfSwKICAgICAgICB7OTIyMzM3MjAzNjg1NDc3NTgwN1VMTCwgMlVMTCwgNDYxMTY4NjAxODQyNzM4NzkwM1VMTCwgMVVMTH0sCiAgICAgICAgezE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCA5MjIzMzcyMDM2ODU0Nzc1ODA3VUxMLCAyVUxMLCAxVUxMfSwKICAgICAgICAvLyDpgornlYzmoYjkvosKICAgICAgICB7MTg0NDY3NDQwNzM3MDk1NTE2MTVVTEwsIDFVTEwsIDE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCAwVUxMfSwKICAgICAgICB7MTg0NDY3NDQwNzM3MDk1NTE2MTVVTEwsIDE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCAxVUxMLCAwVUxMfSwKICAgICAgICB7MFVMTCwgMTg0NDY3NDQwNzM3MDk1NTE2MTVVTEwsIDBVTEwsIDBVTEx9LAogICAgICAgIC8vIOeJueauiuahiOS+iwogICAgICAgIHsxODQ0Njc0NDA3MzcwOTU1MTYxNFVMTCwgMlVMTCwgOTIyMzM3MjAzNjg1NDc3NTgwN1VMTCwgMFVMTH0sCiAgICAgICAgezE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCAyVUxMLCA5MjIzMzcyMDM2ODU0Nzc1ODA3VUxMLCAxVUxMfSwKICAgICAgICB7MTg0NDY3NDQwNzM3MDk1NTE2MTVVTEwsIDNVTEwsIDYxNDg5MTQ2OTEyMzY1MTcyMDVVTEwsIDBVTEx9LAogICAgICAgIC8vIOizquaVuOahiOS+iwogICAgICAgIHsxODQ0Njc0NDA3MzcwOTU1MTU1N1VMTCwgMTFVTEwsIDE2NzY5NzY3MzM5NzM1OTU1OTZVTEwsIDFVTEx9LAogICAgICAgIHsxODQ0Njc0NDA3MzcwOTU1MTU1N1VMTCwgMTg0NDY3NDQwNzM3MDk1NTE1NTdVTEwsIDFVTEwsIDBVTEx9LAogICAgICAgIC8vIDLnmoTlhqrmrKHmlrnmoYjkvosKICAgICAgICB7OTIyMzM3MjAzNjg1NDc3NTgwOFVMTCwgMlVMTCwgNDYxMTY4NjAxODQyNzM4NzkwNFVMTCwgMFVMTH0sCiAgICAgICAgLy8g5aSn5pW46Zmk5LulM1425qGI5L6LCiAgICAgICAgezE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCA3MjlVTEwsIDI1MzA0MTc1Njg2ODQyNDU4VUxMLCA2MDNVTEx9LAogICAgICAgIC8vIOWFtuS7luahiOS+iwogICAgICAgIHsxODQ0Njc0NDA3MzcwOTU1MTYxNVVMTCwgMTBVTEwsIDE4NDQ2NzQ0MDczNzA5NTUxNjFVTEwsIDVVTEx9LAogICAgICAgIHsxODQ0Njc0NDA3MzcwOTU1MTYxNVVMTCwgOTIyMzM3MjAzNjg1NDc3NTgwNlVMTCwgMlVMTCwgM1VMTH0sCiAgICAgICAgezEyMzQ1Njc4OTAxMjM0NTY3ODkwVUxMLCA5ODc2NTQzMjEwOTg3NjU0M1VMTCwgMTI1VUxMLCAwVUxMfSwKICAgICAgICB7MTg0NDY3NDQwNzM3MDk1NTE2MTVVTEwsIDE4NDQ2NzQ0MDczNzA5NTUxNjEwVUxMLCAxVUxMLCA1VUxMfQogICAgfTsKCiAgICBpbnQgbnVtX3Rlc3RzID0gc2l6ZW9mKHRlc3RfY2FzZXMpIC8gc2l6ZW9mKHRlc3RfY2FzZXNbMF0pOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBudW1fdGVzdHM7IGkrKykgewogICAgICAgIHByaW50ZigiVGVzdCBDYXNlICVkOlxuIiwgaSArIDEpOwogICAgICAgIHJ1bl90ZXN0X2Nhc2UodGVzdF9jYXNlc1tpXSk7CiAgICB9CgogICAgcmV0dXJuIDA7Cn0=