Tìm điểm giao đầu tiên của hai cấp số cộng C++

Cho 5 tham số a,b,c,d,n. Hai cấp số cộng:

S1: b, b+a, b+2a, ..., b+(n-1)a
S2: d, d+c, d+2c, ..., d+(n-1)c

Tìm phần tử chung đầu tiên (collision point).

Thuật toán

• Duyệt phần tử của S1 (i từ 0 đến n-1): x = b + i*a.
• Kiểm tra x có thuộc S2 không: x >= d và (x-d) % c == 0.
• Phần tử đầu tiên thỏa mãn là kết quả.

Chương trình C++

#include <bits/stdc++.h>
using namespace std;

void findFirstCollision(int a, int b, int c, int d, int n) {
    for (int i = 0; i < n; i++) {
        long long x = b + 1LL * i * a; // dùng long long tránh tràn
        if (x >= d && (x - d) % c == 0) {
            cout << "First collision point: " << x << " (i=" << i << ")\n";
            return;
        }
    }
    cout << "No collision point found\n";
}

int main() {
    int a = 16, b = 9, c = 23, d = 19, n = 78;
    findFirstCollision(a, b, c, d, n);
    return 0;
}

Kết quả

First collision point: 249 (i=15)

Kiểm tra: S1[15]=9+15×16=249. S2: (249-19)/23=10 → S2[10]=19+10×23=249. ✓