Mod （二分法）

我不是女神ヾ 2022-06-09 04:19 193阅读 0赞

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 <cstdio>
    #include <algorithm>
    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<r)
                    {
                        int mid = (l+r)>>1;
                        if(tmp < a[mid])
                            l = mid+1;
                        else
                            r = mid;
                    }
                    tmp %= a[r];
                    l = r;
                    r = cnt-1;
                    if(tmp<a[r])
                        break;
                }
                printf("%d\n",tmp);
            }
        }
        return 0;
    }