Kim刚刚学会C语言中的取模运算(mod)。他想要研究一下一个数字A模上一系列数后的结果是多少。帮他写个程序验证一下。
Input
第一行一个整数T代表数据组数。
接下来T组数据,第一行一个整数n,接下来n个数字ai
接下来一行一个整数m,接下来m个数字bi。
Output
对于每个bi,输出bi%a1%a2%...%an 。
Sample Input
1
4
10 9 5 7
5
14 8 27 11 25
Sample Output
4
3
2
1
0
Hint
在C语言中,A mod B 是 a%b
样例解释:
14%10%9%5%7=4
8%10%9%5%7=3
...
数据范围:
1<=n<=100000
1<=m<=100000
1<=ai<=1000000000
0<=bi<=1000000000
#include
#include
using namespace std;
#define INF 0x3f3f3f3f
int a[100005];
int main()
{
int t, n, m, tmp, cnt;
scanf("%d",&t);
while(t--)
{
int ok=0,s;
scanf("%d",&n);
a[0] = INF;
cnt = 1;
while(n--)
{
scanf("%d",&tmp);
if(ok==0)
s=tmp;
ok=1;
if(tmp < a[cnt-1])
{
a[cnt] = tmp;
cnt++;
}
}
scanf("%d",&m);
while(m--)
{
scanf("%d",&tmp);
int l=2, r=cnt-1;
tmp%=s;//第一个必须要取模
while(1)
{
while(l>1;
if(tmp < a[mid])
l = mid+1;
else
r = mid;
}
tmp %= a[r];
l = r;
r = cnt-1;
if(tmp