延續取模

延續取模。本站提示廣大學習愛好者：（延續取模）文章只能為提供參考，不一定能成為您想要的結果。以下是延續取模正文

Kim剛剛學會C言語中的取模運算（mod）。他想要研討一下一個數字A模上一系列數後的後果是多少。幫他寫個順序驗證一下。

  第一行一個整數T代表數據組數。

  接上去T組數據，第一行一個整數n，接上去n個數字ai

  接上去一行一個整數m，接上去m個數字bi

關於每個bi,輸入bi%a1%a2%...%an

Input

Output

1

4

10 9 5 7

5

14 8 27 11 25

4

3

2

1

0

在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

思緒：當x延續對一個數列An取模時，後果等於對首項起的遞加數列Bn取模。由於假如對一個小數取模後再對一個大數取模，那麼第二次的操作後後果並沒有變化。

之後，用二分找到與x最接近且小於等於的Bn項，用x模上它，反復這個進程。

#include "cstdio"
#include "algorithm"
#include "cstring"
int s[100000],d[100000];
int b[100000];
int main()
{
    int t,n,m;
    scanf("%d",&t);
    while (t--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&s[i]);
        }
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            scanf("%d",&d[i]);
        }
    }
    b[0]=s[0];
    int k=0;
    for(int i=1;i<n;i++){
        if(b[k]>s[i]){
            b[++k]=s[i];
        }
    }
    for(int i=0;i<m;i++){
        int l=0,x=d[i];
        while (l!=k){
            int r=k;
            while (r>l){
                int mid=(l+r)/2;
                if(x<b[mid]){
                    l=mid+1;
                }
                else{r=mid;}
            }
            x%=b[l];
        }
        printf("%d\n",x);
    }
    return 0;
}