不等式

Time Limit: 10 Sec Memory Limit: 128 MB

Description

小z热衷于数学。
　今天数学课的内容是解不等式：L<=Sx<=R 。小z心想这也太简单了，不禁陷入了深深的思考：假如已知L,R,S,M ，满足L<=(Sx) mod M<=R 的最小正整数x该怎么求呢？

Input

第一行包含一个整数T，表示数据组数，接下来是T行，每行为四个正整数M, S, L, R 。

Output

对于每组数据，输出满足要求的x值，若不存在，输出-1 。

Sample Input

1
　　5 4 2 3

Sample Output

2

HINT

30%的数据中保证有解并且答案小于等于10^6；
　另外20%的数据中保证L=R；
　100%的数据中T<=100，M, S, L, R<=10^9。

Solution

img

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 300005;
const int MOD = 1e9 + 7;

int T;
s64 M, S, L, R;

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

s64 Dfs(s64 M, s64 S, s64 L, s64 R)
{
    if(L > R || M < L) return -1;

    S %= M;
    int res = (L - 1)/S + 1;
    if(res * S <= R) return res;

    int l = (-R % S + S) % S,  r = (-L % S + S) % S;
    int y = Dfs(S, M, l , r); if(y == -1) return -1;

    int x = (R + M * y) / S;
    if(L <= S * x - M * y) return x;
    return -1;
}

int main()
{
    T = get();
    while(T--)
    {
        M = get();    S = get();
        L = get();    R = get();

        printf("%d\n", Dfs(M, S, L, min(R, M-1)));
    }

}