Skip to content

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 read(){
    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)
        a[i] = read() % P, b[i] = read() % P;
    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;
}