Gym 101102J---Divisible Numbers(反推技巧題)，強心髒101102

Gym 101102J---Divisible Numbers(反推技巧題)，強心髒101102

題目鏈接

http://codeforces.com/gym/101102/problem/J

Description

You are given an array A of integers of size N, and Q queries. For each query, you will be given a set of distinct integers S and two integers L and R that represent a range in the array. Your task is to count how many numbers in the given range are divisible by at least one number from the set.

Input

The first line of input contains a single integer T, the number of test cases.

The first line of each test case contains two integers, N and Q (1 ≤ N, Q ≤ 10⁵), the size of the array and the number of queries, respectively.

The next line contains N space-separated integers, the values of the array A (1 ≤ A_i ≤ 10⁹).

Each of the next Q lines contain the description of one query in the form:

LRS

Where L and R (1 ≤ L ≤ R ≤ N) represent the range, and S is an integer between 1 and 1023 (inclusive) and represents the set; consider the binary representation of the number S, if the i^th bit (1-based) is 1, then the number i belongs to the set. Since S is less than1024, the values in the set are between 1 and 10.

For example: if S is equal to 6, the binary representation of 6 is 110, and this means the values in the set are 2 and 3.

The input was given in this way to reduce the size of the input file.

Output

Print the answer for each query on a single line.

Sample Input

1
4 2
2 5 3 8
1 3 2
2 4 355

1
3

題意：輸入n，q表示由n個數構成的一個序列，q次詢問，每次詢問輸入l r s s表示一個集合，s的二進制中的1的位置，如：6（10）=110（2） 對應集合{2,3} 現在求區間l~r中能被集合中的（任意一個）數整除的數的個數；

思路：因為s取值范圍為1~1023 所以輸入n個數時直接求出能被哪些s（對應的集合數）整除，然後用前綴和表示出來，那麼每次查詢時就是0（1）的了；

代碼如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const int MAXN = 1e5+5;
int sum[512][MAXN];
template <class T>
inline void Scan(T &ret)
{
    char c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    ret=c-'0';
    while(c=getchar(),c>='0'&&c<='9')
        ret=ret*10+(c-'0');
}

int main()
{
    int T;
    Scan(T);
    while(T--)
    {
        int n,q,x,s;
        Scan(n); Scan(q);
        ///memset(sum,0,sizeof(sum));  加上超時！！！
        for(int i=1;i<=n;i++)
        {
            s=0;
            Scan(x);
            for(int j=2;j<=10;j++)
                if(x%j==0) s=s|(1<<(j-2));
                
            for(int j=0;j<512;j++)
                sum[j][i]=sum[j][i-1]+((s&j)?1:0);
        }
        while(q--)
        {
            int l,r;
            Scan(l); Scan(r); Scan(x);
            if(x&1) printf("%d\n",r-l+1);
            else    printf("%d\n",sum[x>>1][r]-sum[x>>1][l-1]);
        }
    }
    return 0;
}