HDU 6085 Rikka with Candies （bitset）

Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

There are n children and m kinds of candies. The ith child has Ai dollars and the unit price of the ith kind of candy is Bi. The amount of each kind is infinity.

Each child has his favorite candy, so he will buy this kind of candies as much as possible and will not buy any candies of other kinds. For example, if this child has 10 dollars and the unit price of his favorite candy is 4 dollars, then he will buy two candies and go home with 2 dollars left.

Now Yuta has q queries, each of them gives a number k. For each query, Yuta wants to know the number of the pairs (i,j)(1≤i≤n,1≤j≤m) which satisfies if the ith child’s favorite candy is the jth kind, he will take k dollars home.

To reduce the difficulty, Rikka just need to calculate the answer modulo 2.

But It is still too difficult for Rikka. Can you help her?

Input

The first line contains a number t(1≤t≤5), the number of the testcases.

For each testcase, the first line contains three numbers n,m,q(1≤n,m,q≤50000).

The second line contains n numbers Ai(1≤Ai≤50000) and the third line contains m numbers Bi(1≤Bi≤50000).

Then the fourth line contains q numbers ki(0≤ki

Output

For each query, print a single line with a single 01 digit – the answer.

Sample Input

1
5 5 5
1 2 3 4 5
1 2 3 4 5
0 1 2 3 4      

Sample Output

0
0
0
0
1      

題意

A 數組有 n 個數， B 數組有 m 個數，随後有 q 個查詢，每次輸入一個 k ，詢問有多少對 (i,j) ， 使得 Ai%Bj=k ， 輸出結果模 2

思路

考慮枚舉 k ，顯然隻有當 Bj>k,Ai>=k 時才可能滿足 Ai%Bj=k

Ai%Bj=k 又等價于 Ai−k=Bj×x ，其中 x

我們用 bitset 來存放 A ，于是 bitsetA>>k 相當于 A 中所有元素減去 k ，舍棄小于 0

用 bitsetCNT 來存放 B 的倍數， bitsetCNTi=1 代表有奇數個 j 滿足 i%Bj=0 ，之是以隻統計奇偶數是因為最終對結果模 2

AC 代碼

#include<bits/stdc++.h>

using namespace std;

const int maxn = 5e4+10;

bitset<maxn>a,b;
bitset<maxn>ans,cnt;

void slove(int maxK)
{
    cnt.reset();
    ans.reset();
    for(int i=maxK; i>=0; --i)  //枚舉k
    {
        ans[i]=(cnt&(a>>i)).count()&1;   //存在多少個(a-i)%b=0
        if(b[i])        //枚舉 i 的倍數
            for(int j=0; j<maxn; j+=i)
                cnt.flip(j);
    }
}

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

int main()
{
    int T;
    scan_d(T);
    while(T--)
    {
        int n,m,q;
        scan_d(n);
        scan_d(m);
        scan_d(q);
        a.reset();
        b.reset();
        int maxK=0;
        for(int i=0; i<n; ++i)
        {
            int x;
            scan_d(x);
            a.set(x);
        }
        for(int i=0; i<m; ++i)
        {
            int x;
            scan_d(x);
            b.set(x);
            maxK=max(maxK,x);
        }
        slove(maxK);
        while(q--)
        {
            int x;
            scan_d(x);
            puts(ans[x]?"1":"0");
        }
    }
    return 0;
}