#P1421. A Modular Arithmetic Challenge

    ID: 433 传统题 1000ms 512MiB 尝试: 82 已通过: 31 难度: 8 上传者: 标签>CF2400提高+/省选-模线性不等式最小解向下取整与向上取整

A Modular Arithmetic Challenge

题目描述

求 3≤(3×x) mod 5≤43≤(3\times x) \bmod 5≤4 的最小正整数解是多少?3!这个很简单,但当把数字放得很大呢?

输入格式

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

输出格式

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

1
5 3 3 4
1

提示

T≤100T≤100

1≤M、D、L、R≤10000000001≤M、D、L、R≤1000000000