Tìm phần tử đầu tiên trong cấp số cộng là bội của số nguyên tố cho trước trong C++

Khái niệm

Cho số hạng đầu tiên (A) và công sai (d) của một cấp số cộng, và một số nguyên tố (P). Tìm vị trí của phần tử đầu tiên trong cấp số cộng là bội của P.

Đầu vào

A = 3, d = 4, P = 5

Đầu ra

Giải thích

Số hạng thứ 4 của cấp số cộng là bội của 5.

Số hạng 1 = 3

Số hạng 2 = 3+4 = 7

Số hạng 3 = 3+2*4 = 11

Số hạng 4 = 3+3*4 = 15

Phương pháp

Giả sử số hạng là AN. Khi đó AN = A + (N-1)*d. Vì AN là bội của P: A + (N-1)*d = l*P (l là hằng số).

Thay A = A % P, d = d % P. Khi đó (N-1)*d = (l*P - A). Cộng trừ P ở vế phải: (N-1)*d = P(l-1) + (P-A). Vì A đã mod P nên P-A không âm. Lấy modulo P hai vế: ((N-1)*d)%P = (P-A)%P = P-A.

Tìm Y < P sao cho (d*Y)%P = 1. Y là nghịch đảo modulo của d theo P.

Đáp án N = ((Y*(P-A)) % P) + 1.

Ví dụ

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

int power(int x1, int y1, int p1){
    int res1 = 1;
    x1 = x1 % p1;
    while (y1 > 0) {
        if (y1 & 1)
            res1 = (res1 * x1) % p1;
        y1 = y1 >> 1;
        x1 = (x1 * x1) % p1;
    }
    return res1;
}

int NearestElement1(int A, int d, int P){
    if (A == 0) return 0;
    else if (d == 0) return -1;
    else {
        int Y = power(d, P - 2, P);
        return (Y * (P - A)) % P;
    }
}

int main(){
    int A = 3, d = 4, P = 5;
    A %= P;
    d %= P;
    cout << NearestElement1(A, d, P);
    return 0;
}