Proficient.
Put your skills to the test.

Problem summary

Start with integer N. One operation replaces the current value by (value+A) mod P or (value+B) mod P. Find the minimum operations needed to reach R, or report that it is impossible.

Constraints

0<N≤10^9; 0<A,B≤P≤10^6; 0≤R<P; N≠R.

Worked example

An independently prepared example for this explanation.

20 10
5 5 5

1

Solution analysis

1. All values after the first operation are residues 0 through P−1. Build the graph implicitly: each residue has edges to the residues obtained by adding A or B modulo P.
2. The original N might lie outside this graph. Seed the BFS with both results of its first operation, each at distance 1. This preserves the distinction between N and N mod P; reducing the initial state and assigning it distance zero would be wrong when R=N mod P.
3. For N=20, P=10 and A=B=5, the first resulting residue is 5, so target 5 takes one operation. With A=2, B=4 and target 1, only even residues are reachable and BFS returns −1.

Why it works

Every legal nonempty operation sequence corresponds to a path starting at one of the seeded states, and every such graph path is a legal sequence. BFS explores equal-cost edges by nondecreasing path length, so the first distance assigned to R is minimal.

Watch out. An initial N outside [0,P) is not already the target residue. Deduplicate the two starting states and mark states when enqueuing.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<queue>
// Algorithm: All values after the first operation are residues 0 through P−1.
using namespace std;
int main(){
    long long initial;
    int modulus,addA,addB,target;
    cin>>initial>>modulus>>addA>>addB>>target;
    vector<int>distance(modulus,-1);
    queue<int>pending;
    for(int addition:{addA,addB}){
        int state=static_cast<int>((initial+addition)%modulus);
        if(distance[state]==-1){
            distance[state]=1;
            pending.push(state);
        }
    }
    while(!pending.empty()){
        int current=pending.front();
        pending.pop();
        if(current==target){
            break;
        }
        for(int addition:{addA,addB}){
            int next=(current+addition)%modulus;
            if(distance[next]==-1){
                distance[next]=distance[current]+1;
                pending.push(next);
            }
        }
    }
    cout<<distance[target]<<'\n';
}