#P9268. 加减AB操作

    ID: 5573 传统题 12000ms 888MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-无向连通分量缩点类欧几里得算法二分查找

加减AB操作

题面翻译

给定整数 A,B,V,MA,B,V,M,其中 A,BA,B 保证互质。另外,还有一个整数 xx,初始化为 x=Vx=V。

您可以按任意顺序执行以下四种操作,次数不限。

将 xx 的值修改为 x+Ax+A

将 xx 的值修改为 x−Ax-A

将 xx 的值修改为 x+Bx+B

将 xx 的值修改为 x−Bx-B

在操作过程中,0≤x≤M0\le x \le M 必须在任意时刻成立。

问在这种情况下,xx 可以取多少不同的值。

多组数据。

样例 #1

样例输入 #1

5
3 5 0 5
1 2 5 10
5 8 4 9
10 99 48 106
500000000 500000001 123456789 900000000

样例输出 #1

4
11
4
10
800000002

提示

制約

  • 1 ≤ T ≤ 105 1\ \leq\ T\ \leq\ 10^5
  • 1 ≤ A < B ≤ M ≤ 109 1\ \leq\ A\ <\ B\ \leq\ M\ \leq\ 10^9
  • A A と B B は互いに素である.
  • 0 ≤ V ≤ M 0\ \leq\ V\ \leq\ M