ในคณิตศาสตร์ Modular Equation คือ สมการทางพีชคณิตที่เกี่ยวข้องกับ Moduli โจทย์: มีจำนวนเต็ม a, b หาจำนวนค่า x ที่เป็นไปได้ สำหรับสมการ (A mod X) = B โดย X เป็นคำตอบ
ตัวอย่าง:
Input: A = 26, B = 2 Output: X can take 6 values
คำอธิบาย
X ใน {3, 4, 6, 8, 12, 24} เพราะ 26 mod ทุกค่า = 2
เงื่อนไข:
- A = B -> X มีค่าได้มากมาย (Infinite) โดย A > X เสมอ
- A < B -> ไม่มี X ใดทำให้สมการเป็นจริง
- A > B -> ใช้ความสัมพันธ์ Dividend = Divisor * Quotient + Remainder
A = X * Y + B (Y = Quotient) -> A - B = X * Y -> X ต้องหาร (A - B) ลงตัว
ดังนั้น X คือ ตัวหารของ (A - B) ที่มากกว่า B จำนวนตัวหารดังกล่าวคือคำตอบ
ตัวอย่าง
#include <iostream>
#include <math.h>
using namespace std;
int Divisors(int A, int B) {
int N = (A - B);
int D = 0;
for (int i = 1; i <= sqrt(N); i++) {
if ((N % i) == 0) {
if (i > B) D++;
if ((N / i) != i && (N / i) > B) D++;
}
}
return D;
}
int PossibleWaysUtil(int A, int B) {
if (A == B) return -1;
if (A < B) return 0;
return Divisors(A, B);
}
int main() {
int A = 26, B = 2;
int Sol = PossibleWaysUtil(A, B);
if (Sol == -1) {
cout << "X can take Infinitely many values greater than " << A << "\n";
} else {
cout << "X can take " << Sol << " values\n";
return 0;
}
}