题目详情题解（0）讨论（0）提交记录（0）

CF1673D.Lost Arithmetic Progression

普及+/提高

通过率：0%

时间限制：1.00s

内存限制：256MB

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Long ago, you thought of two finite arithmetic progressions AA and BB. Then you found out another sequence CC containing all elements common to both AA and BB. It is not hard to see that CC is also a finite arithmetic progression. After many years, you forgot what AA was but remember BB and CC. You are, for some reason, determined to find this lost arithmetic progression. Before you begin this eternal search, you want to know how many different finite arithmetic progressions exist which can be your lost progression AA.

Two arithmetic progressions are considered different if they differ in their first term, common difference or number of terms.

It may be possible that there are infinitely many such progressions, in which case you won't even try to look for them! Print −1-1 in all such cases.

Even if there are finite number of them, the answer might be very large. So, you are only interested to find the answer modulo 109+710^9+7.

很久以前，你构思了两个有限的等差数列 AA 和 BB。随后，你发现了另一个序列 CC，它包含 AA 与 BB 的所有公共元素。不难看出，CC 本身也是一个有限等差数列。多年以后，你忘记了 AA 的具体形式，但还记得 BB 和 CC。出于某种原因，你决心找回这个遗失的等差数列。但在开始这场永恒的搜寻之前，你想先知道：有多少个不同的有限等差数列可以作为你遗失的 AA。

若两个等差数列的首项、公差或项数中至少有一项不同，则认为它们是不同的。

有可能存在无穷多个满足条件的等差数列；此时你甚至不会尝试去寻找它们！所有此类情况均输出 −1-1。

即使满足条件的等差数列数量有限，答案也可能非常大。因此，你只需输出答案对 109+710^9+7 取模的结果。

输入格式

The first line of input contains a single integer tt (1≤t≤1001\leq t\leq 100) denoting the number of testcases.

The first line of each testcase contains three integers bb, qq and yy (−109≤b≤109-10^9\leq b\leq 10^9, 1≤q≤1091\leq q\leq 10^9, 2≤y≤1092\leq y\leq 10^9) denoting the first term, common difference and number of terms of BB respectively.

The second line of each testcase contains three integers cc, rr and zz (−109≤c≤109-10^9\leq c\leq 10^9, 1≤r≤1091\leq r\leq 10^9, 2≤z≤1092\leq z\leq 10^9) denoting the first term, common difference and number of terms of CC respectively.

输入的第一行包含一个整数 tt（1≤t≤1001\leq t\leq 100），表示测试用例的数量。

每个测试用例的第一行包含三个整数 bb、qq 和 yy（−109≤b≤109-10^9\leq b\leq 10^9，1≤q≤1091\leq q\leq 10^9，2≤y≤1092\leq y\leq 10^9），分别表示等差数列 BB 的首项、公差和项数。

每个测试用例的第二行包含三个整数 cc、rr 和 zz（−109≤c≤109-10^9\leq c\leq 10^9，1≤r≤1091\leq r\leq 10^9，2≤z≤1092\leq z\leq 10^9），分别表示等差数列 CC 的首项、公差和项数。

输出格式

For each testcase, print a single line containing a single integer.

If there are infinitely many finite arithmetic progressions which could be your lost progression AA, print −1-1.

Otherwise, print the number of finite arithmetic progressions which could be your lost progression AA modulo 109+710^9+7. In particular, if there are no such finite arithmetic progressions, print 00.

对于每个测试用例，输出一行，包含一个整数。

如果存在无穷多个可能的有限等差数列 AA 满足条件，则输出 −1-1。

否则，输出满足条件的有限等差数列 AA 的个数对 109+710^9+7 取模的结果。特别地，若不存在任何满足条件的有限等差数列，则输出 00。

输入输出样例

  • 输入#1

    8
-3 1 7
-1 2 4
-9 3 11
0 6 3
2 5 5
7 5 4
2 2 11
10 5 3
0 2 9
2 4 3
-11 4 12
1 12 2
-27 4 7
-17 8 2
-8400 420 1000000000
0 4620 10

    输出#1

    0
10
-1
0
-1
21
0
273000

说明/提示

For the first testcase, B=−3,−2,−1,0,1,2,3B={-3,-2,-1,0,1,2,3} and C=−1,1,3,5C={-1,1,3,5}. There is no such arithmetic progression which can be equal to AA because 55 is not present in BB and for any AA, 55 should not be present in CC also.

For the second testcase, B=−9,−6,−3,0,3,6,9,12,15,18,21B={-9,-6,-3,0,3,6,9,12,15,18,21} and C=0,6,12C={0,6,12}. There are 1010 possible arithmetic progressions which can be AA:

  • 0,6,12{0,6,12}
  • 0,2,4,6,8,10,12{0,2,4,6,8,10,12}
  • 0,2,4,6,8,10,12,14{0,2,4,6,8,10,12,14}
  • 0,2,4,6,8,10,12,14,16{0,2,4,6,8,10,12,14,16}
  • −2,0,2,4,6,8,10,12{-2,0,2,4,6,8,10,12}
  • −2,0,2,4,6,8,10,12,14{-2,0,2,4,6,8,10,12,14}
  • −2,0,2,4,6,8,10,12,14,16{-2,0,2,4,6,8,10,12,14,16}
  • −4,−2,0,2,4,6,8,10,12{-4,-2,0,2,4,6,8,10,12}
  • −4,−2,0,2,4,6,8,10,12,14{-4,-2,0,2,4,6,8,10,12,14}
  • −4,−2,0,2,4,6,8,10,12,14,16{-4,-2,0,2,4,6,8,10,12,14,16}

For the third testcase, B=2,7,12,17,22B={2,7,12,17,22} and C=7,12,17,22C={7,12,17,22}. There are infinitely many arithmetic progressions which can be AA like:

  • 7,12,17,22{7,12,17,22}
  • 7,12,17,22,27{7,12,17,22,27}
  • 7,12,17,22,27,32{7,12,17,22,27,32}
  • 7,12,17,22,27,32,37{7,12,17,22,27,32,37}
  • 7,12,17,22,27,32,37,42{7,12,17,22,27,32,37,42}
  • …\ldots

对于第一个测试用例，B=−3,−2,−1,0,1,2,3B={-3,-2,-1,0,1,2,3}，C=−1,1,3,5C={-1,1,3,5}。不存在满足条件的等差数列 AA，因为 5∉B5 \notin B，且对任意 AA，55 也不应出现在 CC 中。

对于第二个测试用例，B=−9,−6,−3,0,3,6,9,12,15,18,21B={-9,-6,-3,0,3,6,9,12,15,18,21}，C=0,6,12C={0,6,12}。共有 1010 个可能的等差数列 AA：

  • 0,6,12{0,6,12}
  • 0,2,4,6,8,10,12{0,2,4,6,8,10,12}
  • 0,2,4,6,8,10,12,14{0,2,4,6,8,10,12,14}
  • 0,2,4,6,8,10,12,14,16{0,2,4,6,8,10,12,14,16}
  • −2,0,2,4,6,8,10,12{-2,0,2,4,6,8,10,12}
  • −2,0,2,4,6,8,10,12,14{-2,0,2,4,6,8,10,12,14}
  • −2,0,2,4,6,8,10,12,14,16{-2,0,2,4,6,8,10,12,14,16}
  • −4,−2,0,2,4,6,8,10,12{-4,-2,0,2,4,6,8,10,12}
  • −4,−2,0,2,4,6,8,10,12,14{-4,-2,0,2,4,6,8,10,12,14}
  • −4,−2,0,2,4,6,8,10,12,14,16{-4,-2,0,2,4,6,8,10,12,14,16}

对于第三个测试用例，B=2,7,12,17,22B={2,7,12,17,22}，C=7,12,17,22C={7,12,17,22}。存在无穷多个可能的等差数列 AA，例如：

  • 7,12,17,22{7,12,17,22}
  • 7,12,17,22,27{7,12,17,22,27}
  • 7,12,17,22,27,32{7,12,17,22,27,32}
  • 7,12,17,22,27,32,37{7,12,17,22,27,32,37}
  • 7,12,17,22,27,32,37,42{7,12,17,22,27,32,37,42}
  • …\ldots

输入解题思路，AI测评打分。不知道怎么写?

首页