# 11096: 【原1096】Candy

### 题目描述

author: Guangda Huzhang 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1096

## Description

You have $$S$$ candies in your hands, and there are $$M$$ machines in front of you. Now you can do following operations:

• If you have candies, you can put all your candies into the i-th machine (you can't keep any candies).

Then waiting for a while, the i-th machine will return you $$[(A_i \times n + B_i) \mod P]$$ candies if you put $$n$$ candies into it.

• Do nothing, you still have your candies.

If your goal is to get $$T$$ candies at last, what is the minimum number of times you need to operate machines.

## Input Format

Input includes several test cases. For each test case, the first line contains four non-negative integers $$S, T, M, P (P > 0, M \times P \leq 10^6)$$. The following $$M$$ lines contain details of $$M$$ machines. For each line, there are two integers $$A_i, B_i$$.

We guarantee every integer of input is in the range of 32-bit signed integer.

The input ends by EOF.

## Output Format

For each test case, if you can get $$T$$ candies at last, output a single integer indicates the minimum number of operations, otherwise output -1.

## Sample Input

3 1 2 4
1 1
1 2


## Sample Output

1


## Case Limits

Time limit: 500 msec

Memory limit: 64 MB

## zqy2018's solution

#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int S, T, M, P;
int a[1000005], b[1000005];
int dis[1000005];
int que[1000005], hd, tl;
void init(){
for (int i = 1; i <= M; ++i)
memset(dis, 0x3f, sizeof(dis));
}
void solve(){
if (S == T){
printf("0\n");
return ;
}
if (T >= P) {
printf("-1\n");
return ;
}
hd = tl = 0;
if (S < P) dis[S] = 0;
/* warning: S may be larger than P. */
S %= P;
for (int i = 1; i <= M; ++i){
int t = (1ll * a[i] * S + b[i]) % P;
if (dis[t] == 1) continue;
dis[t] = 1;
if (t == T){
printf("%d\n", dis[t]);
return ;
}
que[tl++] = t;
}
while (tl > hd){
int h = que[hd++];
for (int i = 1; i <= M; ++i){
int t = (1ll * a[i] * h + b[i]) % P;
if (dis[t] <= dis[h] + 1)
continue;
dis[t] = dis[h] + 1;
if (t == T){
printf("%d\n", dis[t]);
return ;
}
que[tl++] = t;
}
}
printf("-1\n");
}
int main(){
while (scanf("%d%d%d%d", &S, &T, &M, &P) == 4){
init();
solve();
}
return 0;
}