#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},
        {9223372036854775808ULL, 2ULL, 4611686018427387904ULL, 0ULL},
 
        // 新增的測試案例
        // 大數除以小數
        {18446744073709551615ULL, 10ULL, 1844674407370955161ULL, 5ULL},
 
        // 接近 2^64 的數除以接近 2^63 的數
        {18446744073709551615ULL, 9223372036854775806ULL, 2ULL, 3ULL},
 
        // 質數除法
        {18446744073709551557ULL, 17ULL, 1085102592571150091ULL, 10ULL},
 
        // 連續數字除法
        {12345678901234567890ULL, 98765432109876543ULL, 124ULL, 98765319609876558ULL},
 
        // 大數除以 1
        {18446744073709551615ULL, 1ULL, 18446744073709551615ULL, 0ULL},
 
        // 0 除以任何數
        {0ULL, 12345ULL, 0ULL, 0ULL},
 
        // 任何數除以自己
        {12345678901234567890ULL, 12345678901234567890ULL, 1ULL, 0ULL},
 
        // 2 的冪次方除法
        {1ULL << 63, 1ULL << 31, 1ULL << 32, 0ULL},
 
        // 大數除以大數，結果為小數
        {18446744073709551615ULL, 18446744073709551614ULL, 1ULL, 1ULL},
 
        // Fibonacci 數列相鄰項的除法
        {17711ULL, 10946ULL, 1ULL, 6765ULL},  // F(22) / F(21)
 
        // 大數除以 3 的冪次方
        {18446744073709551615ULL, 729ULL, 25304175686842458ULL, 603ULL},  // (2^64 - 1) / 3^6
 
        // 接近 2^64 的數除以接近自身的數
        {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]);
        #if 0
        if (test.dividend != test.divisor * test.expected_quotient + test.expected_remainder) {
    		printf("Warning: Test case may be incorrect!\n");
		}
		#endif
    }
    return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRpbnQuaD4KdHlwZWRlZiB1aW50NjRfdCB1NjQ7CgovLyDkv67mlLnlvoznmoTpmaTms5Xlh73mlbjvvIzov5Tlm57llYblkozppJjmlbgKdm9pZCBudm1lX3U2NF9kaXYodTY0IGRpdmlkZW5kLCB1NjQgZGl2aXNvciwgdTY0KiBxdW90aWVudCwgdTY0KiByZW1haW5kZXIpIHsKICAgICpxdW90aWVudCA9IDA7CiAgICAqcmVtYWluZGVyID0gMDsKICAgIGludCBpOwogICAgZm9yIChpID0gNjM7IGkgPj0gMDsgaS0tKSB7CiAgICAgICAgKnJlbWFpbmRlciA9ICgqcmVtYWluZGVyIDw8IDEpIHwgKChkaXZpZGVuZCA+PiBpKSAmIDEpOwogICAgICAgIGlmICgqcmVtYWluZGVyID49IGRpdmlzb3IpIHsKICAgICAgICAgICAgKnJlbWFpbmRlciAtPSBkaXZpc29yOwogICAgICAgICAgICAqcXVvdGllbnQgfD0gKDFVTEwgPDwgaSk7CiAgICAgICAgfQogICAgfQp9CgovLyDmuKzoqabmoYjkvovntZDmp4sKdHlwZWRlZiBzdHJ1Y3QgewogICAgdTY0IGRpdmlkZW5kOwogICAgdTY0IGRpdmlzb3I7CiAgICB1NjQgZXhwZWN0ZWRfcXVvdGllbnQ7CiAgICB1NjQgZXhwZWN0ZWRfcmVtYWluZGVyOwp9IFRlc3RDYXNlOwoKLy8g5Z+36KGM5ris6Kmm5Lim5omT5Y2w57WQ5p6cCnZvaWQgcnVuX3Rlc3RfY2FzZShUZXN0Q2FzZSB0ZXN0KSB7CiAgICB1NjQgcXVvdGllbnQsIHJlbWFpbmRlcjsKICAgIG52bWVfdTY0X2Rpdih0ZXN0LmRpdmlkZW5kLCB0ZXN0LmRpdmlzb3IsICZxdW90aWVudCwgJnJlbWFpbmRlcik7CiAgICAKICAgIHByaW50ZigiRGl2aWRlbmQ6ICVsbHVcbiIsIHRlc3QuZGl2aWRlbmQpOwogICAgcHJpbnRmKCJEaXZpc29yOiAlbGx1XG4iLCB0ZXN0LmRpdmlzb3IpOwogICAgcHJpbnRmKCJFeHBlY3RlZCBRdW90aWVudDogJWxsdVxuIiwgdGVzdC5leHBlY3RlZF9xdW90aWVudCk7CiAgICBwcmludGYoIkFjdHVhbCBRdW90aWVudDogJWxsdVxuIiwgcXVvdGllbnQpOwogICAgcHJpbnRmKCJFeHBlY3RlZCBSZW1haW5kZXI6ICVsbHVcbiIsIHRlc3QuZXhwZWN0ZWRfcmVtYWluZGVyKTsKICAgIHByaW50ZigiQWN0dWFsIFJlbWFpbmRlcjogJWxsdVxuIiwgcmVtYWluZGVyKTsKICAgIHByaW50ZigiVGVzdCAlc1xuXG4iLCAKICAgICAgICAgICAocXVvdGllbnQgPT0gdGVzdC5leHBlY3RlZF9xdW90aWVudCAmJiByZW1haW5kZXIgPT0gdGVzdC5leHBlY3RlZF9yZW1haW5kZXIpIAogICAgICAgICAgID8gIlBBU1NFRCIgOiAiRkFJTEVEIik7Cn0KCmludCBtYWluKCkgewogICAgLy8g5pO05bGV55qE5ris6Kmm5qGI5L6L5pW457WECiAgICBUZXN0Q2FzZSB0ZXN0X2Nhc2VzW10gPSB7CiAgICAgICAgLy8g5Y6f5pyJ55qE5ris6Kmm5qGI5L6LCiAgICAgICAgezEwMDAwMDAwMDAwMDAwMDAwMDBVTEwsIDNVTEwsIDMzMzMzMzMzMzMzMzMzMzMzM1VMTCwgMVVMTH0sCiAgICAgICAgezkyMjMzNzIwMzY4NTQ3NzU4MDdVTEwsIDJVTEwsIDQ2MTE2ODYwMTg0MjczODc5MDNVTEwsIDFVTEx9LAogICAgICAgIHsxODQ0Njc0NDA3MzcwOTU1MTYxNVVMTCwgOTIyMzM3MjAzNjg1NDc3NTgwN1VMTCwgMlVMTCwgMVVMTH0sCiAgICAgICAgezE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCAxVUxMLCAxODQ0Njc0NDA3MzcwOTU1MTYxNVVMTCwgMFVMTH0sCiAgICAgICAgezE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCAxODQ0Njc0NDA3MzcwOTU1MTYxNVVMTCwgMVVMTCwgMFVMTH0sCiAgICAgICAgezBVTEwsIDE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCAwVUxMLCAwVUxMfSwKICAgICAgICB7MTg0NDY3NDQwNzM3MDk1NTE2MTRVTEwsIDJVTEwsIDkyMjMzNzIwMzY4NTQ3NzU4MDdVTEwsIDBVTEx9LAogICAgICAgIHsxODQ0Njc0NDA3MzcwOTU1MTYxNVVMTCwgMlVMTCwgOTIyMzM3MjAzNjg1NDc3NTgwN1VMTCwgMVVMTH0sCiAgICAgICAgezE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCAzVUxMLCA2MTQ4OTE0NjkxMjM2NTE3MjA1VUxMLCAwVUxMfSwKICAgICAgICB7MTg0NDY3NDQwNzM3MDk1NTE1NTdVTEwsIDExVUxMLCAxNjc2OTc2NzM0MTU1NDEzNzc4VUxMLCA5VUxMfSwKICAgICAgICB7MTg0NDY3NDQwNzM3MDk1NTE1NTdVTEwsIDE4NDQ2NzQ0MDczNzA5NTUxNTU3VUxMLCAxVUxMLCAwVUxMfSwKICAgICAgICB7OTIyMzM3MjAzNjg1NDc3NTgwOFVMTCwgMlVMTCwgNDYxMTY4NjAxODQyNzM4NzkwNFVMTCwgMFVMTH0sCiAgICAgICAgCiAgICAgICAgLy8g5paw5aKe55qE5ris6Kmm5qGI5L6LCiAgICAgICAgLy8g5aSn5pW46Zmk5Lul5bCP5pW4CiAgICAgICAgezE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCAxMFVMTCwgMTg0NDY3NDQwNzM3MDk1NTE2MVVMTCwgNVVMTH0sCiAgICAgICAgCiAgICAgICAgLy8g5o6l6L+RIDJeNjQg55qE5pW46Zmk5Lul5o6l6L+RIDJeNjMg55qE5pW4CiAgICAgICAgezE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCA5MjIzMzcyMDM2ODU0Nzc1ODA2VUxMLCAyVUxMLCAzVUxMfSwKICAgICAgICAKICAgICAgICAvLyDos6rmlbjpmaTms5UKICAgICAgICB7MTg0NDY3NDQwNzM3MDk1NTE1NTdVTEwsIDE3VUxMLCAxMDg1MTAyNTkyNTcxMTUwMDkxVUxMLCAxMFVMTH0sCiAgICAgICAgCiAgICAgICAgLy8g6YCj57qM5pW45a2X6Zmk5rOVCiAgICAgICAgezEyMzQ1Njc4OTAxMjM0NTY3ODkwVUxMLCA5ODc2NTQzMjEwOTg3NjU0M1VMTCwgMTI0VUxMLCA5ODc2NTMxOTYwOTg3NjU1OFVMTH0sCiAgICAgICAgCiAgICAgICAgLy8g5aSn5pW46Zmk5LulIDEKICAgICAgICB7MTg0NDY3NDQwNzM3MDk1NTE2MTVVTEwsIDFVTEwsIDE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCAwVUxMfSwKICAgICAgICAKICAgICAgICAvLyAwIOmZpOS7peS7u+S9leaVuAogICAgICAgIHswVUxMLCAxMjM0NVVMTCwgMFVMTCwgMFVMTH0sCiAgICAgICAgCiAgICAgICAgLy8g5Lu75L2V5pW46Zmk5Lul6Ieq5bexCiAgICAgICAgezEyMzQ1Njc4OTAxMjM0NTY3ODkwVUxMLCAxMjM0NTY3ODkwMTIzNDU2Nzg5MFVMTCwgMVVMTCwgMFVMTH0sCiAgICAgICAgCiAgICAgICAgLy8gMiDnmoTlhqrmrKHmlrnpmaTms5UKICAgICAgICB7MVVMTCA8PCA2MywgMVVMTCA8PCAzMSwgMVVMTCA8PCAzMiwgMFVMTH0sCiAgICAgICAgCiAgICAgICAgLy8g5aSn5pW46Zmk5Lul5aSn5pW477yM57WQ5p6c54K65bCP5pW4CiAgICAgICAgezE4NDQ2NzQ0MDczNzA5NTUxNjE1VUxMLCAxODQ0Njc0NDA3MzcwOTU1MTYxNFVMTCwgMVVMTCwgMVVMTH0sCiAgICAgICAgCiAgICAgICAgLy8gRmlib25hY2NpIOaVuOWIl+ebuOmEsOmgheeahOmZpOazlQogICAgICAgIHsxNzcxMVVMTCwgMTA5NDZVTEwsIDFVTEwsIDY3NjVVTEx9LCAgLy8gRigyMikgLyBGKDIxKQogICAgICAgIAogICAgICAgIC8vIOWkp+aVuOmZpOS7pSAzIOeahOWGquasoeaWuQogICAgICAgIHsxODQ0Njc0NDA3MzcwOTU1MTYxNVVMTCwgNzI5VUxMLCAyNTMwNDE3NTY4Njg0MjQ1OFVMTCwgNjAzVUxMfSwgIC8vICgyXjY0IC0gMSkgLyAzXjYKICAgICAgICAKICAgICAgICAvLyDmjqXov5EgMl42NCDnmoTmlbjpmaTku6XmjqXov5Hoh6rouqvnmoTmlbgKICAgICAgICB7MTg0NDY3NDQwNzM3MDk1NTE2MTVVTEwsIDE4NDQ2NzQ0MDczNzA5NTUxNjEwVUxMLCAxVUxMLCA1VUxMfQogICAgfTsKICAgIAogICAgaW50IG51bV90ZXN0cyA9IHNpemVvZih0ZXN0X2Nhc2VzKSAvIHNpemVvZih0ZXN0X2Nhc2VzWzBdKTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbnVtX3Rlc3RzOyBpKyspIHsKICAgICAgICBwcmludGYoIlRlc3QgQ2FzZSAlZDpcbiIsIGkgKyAxKTsKICAgICAgICBydW5fdGVzdF9jYXNlKHRlc3RfY2FzZXNbaV0pOwogICAgICAgICNpZiAwCiAgICAgICAgaWYgKHRlc3QuZGl2aWRlbmQgIT0gdGVzdC5kaXZpc29yICogdGVzdC5leHBlY3RlZF9xdW90aWVudCArIHRlc3QuZXhwZWN0ZWRfcmVtYWluZGVyKSB7CiAgICAJCXByaW50ZigiV2FybmluZzogVGVzdCBjYXNlIG1heSBiZSBpbmNvcnJlY3QhXG4iKTsKCQl9CgkJI2VuZGlmCiAgICB9CiAgICByZXR1cm4gMDsKfQ==