#P1320. Pku3530A Modular Arithmetic Challenge

    ID: 332 传统题 1000ms 512MiB 尝试: 141 已通过: 36 难度: 7 上传者: 标签>CF2300提高+/省选-类欧几里得算法二分答案向下取整与向上取整交换求和顺序

Pku3530A Modular Arithmetic Challenge

题目描述

求 L≤(D×x) mod M≤RL\leq (D\times x) \bmod M\leq R 的最小正整数解

输入格式

第一行一个整数。T代表数据组数。 接下来T行,每行4个数,M,D,L,R表示L≤(D×x) mod M≤RL\leq (D\times x) \bmod M\leq R。

输出格式

共 TT 行,表示 xx 的最小正整数解,若无解则输出-1。

1
5 3 3 4
1

提示

T<=100,1<=M、D、L、R<=1000000000T<=100,1<=M、D、L、R<=1000000000