hdu1573

maksyuki 发表于 oj 分类,标签:
0

X问题

Problem Description

求在小于等于N的正整数中有多少个X满足:X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 < a[i] <= 10)。

Input

输入数据的第一行为一个正整数T,表示有T组测试数据。每组测试数据的第一行为两个正整数N,M (0 < N <= 1000,000,000 , 0 < M <= 10),表示X小于等于N,数组a和b中各有M个元素。接下来两行,每行各有M个正整数,分别为a和b中的元素。

Output

对应每一组输入,在独立一行中输出一个正整数,表示满足条件的X的个数。

Sample Input

3

10 3

1 2 3

0 1 2

100 7

3 4 5 6 7 8 9

1 2 3 4 5 6 7

10000 10

1 2 3 4 5 6 7 8 9 10

0 1 2 3 4 5 6 7 8 9

Sample Output

1

0

3

Author

lwg

Source

HDU 2007-1 Programming Contest

 

题目类型:线性同余方程组

算法分析:首先计算出方程组的最小非负整数解,如果没有解则直接输出0,反之使用tot += (val - x0) / ans计算在val范围内的解数量,其中ans表示lcm (a1, a2, a3, ……an),注意题目要求输出正整数解,所以初始解为0时要排除掉