#3992. X问题

    ID: 3992 传统题 1000ms 32MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>中国剩余定理线性同余方程信息学奥赛之数学一本通习题1.11.8

X问题

题目描述

求在小于等于NN的正整数中有多少个XX满足:

X mod a[0] = b[0]
X mod a[1] = b[1]
X mod a[2] = b[2]
…
X mod a[i] = b[i],
…

输入格式

输入数据的第一行为一个正整数TT,表示有TT组测试数据。

每组测试数据的第一行为两个正整数NM,N,M, 表示XX小于等于NN,数组aabb中各有MM个元素。接下来两行,每行各有MM个正整数,分别为aabb中的元素。

输出格式

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

样例

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
1
0
3

数据范围

  • 0<a[i]100 < a[i] \le 10
  • 0<N1000,000,000;0<M100 < N \le 1000,000,000 ; 0 < M \le 10

来源

  • HDU1573
  • 信息学奥赛之数学一本通
  • stong9070整理