Lab 6-3: 大數取餘數 (15%)
Division algorithm - Wikipedia
可以參考以下正整數取餘數的 pseudocode：
R = N
while R >= D do
R = R - D
end
return R
- 輸入：
- 兩自然數字 \( N, D \) 並且各自不多於 36 位數字。
- 兩自然數字的前後 18 位數字需分別輸入。
- \( N = N_{first} \times 10^{18} + N_{second}, D = D_{first} \times 10^{18} + D_{second} \)
- 需偵測不合法的輸入，並輸出
Invalid input後提示使用者再次輸入該自然數。 - 需支援重複輸入，使用者輸入
-1則結束程式。
- 輸出：兩自然數字 \( N, D \) 及相除的餘數 \( N % D \)。
- 檔名：lab6_3_<學號>.cpp (e.g. lab6_3_106062802.cpp)
程式需提示使用者輸入兩自然數字 \( N, D \)，輸出兩自然數字相除的餘數 \( N % D \)。
使用者會在每次輸入時輸入任意整數，請考慮所有合法 long long 型態的數字輸入。
The number N, first part (input -1 to exit): <N_first>⏎
The number N, second part (input -1 to exit): <N_second>⏎
The number N = <N>
The number D, first part (input -1 to exit): <D_first>⏎
The number D, second part (input -1 to exit): <D_second>⏎
The number D = <D>
The remainder N % D = <N % D>
Example:
$ ./a.out
The number N, first part (input -1 to exit): 2⏎
The number N, second part (input -1 to exit): 2⏎
The number N = 2000000000000000002
The number D, first part (input -1 to exit): 1⏎
The number D, second part (input -1 to exit): 0⏎
The number D = 1000000000000000000
The remainder N % D = 2
The number N, first part (input -1 to exit): 1234567890123456789⏎
Invalid input
The number N, first part (input -1 to exit): 123456789123456789⏎
The number N, second part (input -1 to exit): 1234567890123456789⏎
Invalid input
The number N, first part (input -1 to exit): 123456789123456789⏎
The number N, second part (input -1 to exit): 123456789123456789⏎
The number N = 123456789123456789123456789123456789
The number D, first part (input -1 to exit): 1111111110111111111⏎
Invalid input
The number D, first part (input -1 to exit): 111111111111111111⏎
The number D, second part (input -1 to exit): 1111111110111111111⏎
Invalid input
The number D, first part (input -1 to exit): 111111111111111111⏎
The number D, second part (input -1 to exit): 111111111111111111⏎
The number D = 111111111111111111111111111111111111
The remainder N % D = 12345678012345678012345678012345678
The number N, first part (input -1 to exit): -1⏎
$ ./a.out
The number N, first part (input -1 to exit): -2⏎
Invalid input
The number N, first part (input -1 to exit): 1⏎
The number N, second part (input -1 to exit): -2⏎
Invalid input
The number N, first part (input -1 to exit): 2⏎
The number N, second part (input -1 to exit): 2⏎
The number N = 2000000000000000002
The number D, first part (input -1 to exit): -1⏎
Reference:
Reference Code:
Credit: 林暐晉(110021134)
#include <iostream>
#include <iomanip>
#include <math.h>
using namespace std;
int main()
{
unsigned long long long_a_a = 0, long_a_b = 0, long_b_a = 0, long_b_b = 0;
while (1)
{
while (cout << "The number N, first part (input -1 to exit): ")
{
cin >> long_a_a;
if (long_a_a == -1)
{
return 0;
}
if (long_a_a < 0 || long_a_a >= (long long)pow(10, 18))
{
cout << "Invalid input" << endl;
continue;
}
cout << "The number N, second part (input -1 to exit): ";
cin >> long_a_b;
if (long_a_b == -1)
{
return 0;
}
if (long_a_b < 0 || long_a_b >= (long long)pow(10, 18))
{
cout << "Invalid input" << endl;
continue;
}
if (long_a_a == 0 && long_a_b == 0)
{
cout << "Invalid input" << endl;
continue;
}
if (long_a_a == 0)
{
cout << "The number N = " << long_a_b << endl;
}
else
{
cout << "The number N = " << long_a_a << setfill('0') << setw(18) << long_a_b << endl;
}
break;
}
while (cout << "The number D, first part (input -1 to exit): ")
{
cin >> long_b_a;
if (long_b_a == -1)
{
return 0;
}
if (long_b_a < 0 || long_b_a >= (long long)pow(10, 18))
{
cout << "Invalid input" << endl;
continue;
}
cout << "The number D, second part (input -1 to exit): ";
cin >> long_b_b;
if (long_b_b == -1)
{
return 0;
}
if (long_b_b < 0 || long_b_b >= (long long)pow(10, 18))
{
cout << "Invalid input" << endl;
continue;
}
if (long_b_a == 0 && long_b_b == 0)
{
cout << "Invalid input" << endl;
continue;
}
if (long_b_a == 0)
{
cout << "The number D = " << long_b_b << endl;
}
else
{
cout << "The number D = " << long_b_a << setfill('0') << setw(18) << long_b_b << endl;
}
break;
}
while (long_a_a >= long_b_a)
{
if (long_b_a == 0 && long_b_b != 0)
{
long_a_b %= long_b_b;
long_a_a--;
if (long_a_a > (long long)pow(10, 18))
{
long_a_a++;
break;
}
long_a_b += (long long)pow(10, 18);
}
else
{
long_a_a -= long_b_a;
if (long_a_b < long_b_b)
{
long_a_a--;
if (long_a_a > (long long)pow(10, 18))
{
long_a_a++;
long_a_a += long_b_a;
break;
}
long_a_b += (long long)pow(10, 18);
long_a_b -= long_b_b;
}
else
{
long_a_b -= long_b_b;
}
}
}
if (long_a_a == 0)
{
cout << "The remainder N % D = " << long_a_b << endl;
}
else
{
cout << "The remainder N % D = " << long_a_a << setfill('0') << setw(18) << long_a_b << endl;
}
cout << endl;
}
return 0;
}