程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> CSU1661: Query Mutiple

CSU1661: Query Mutiple

編輯：關於C++

Description

One day，Little-Y saw many numbers standing in a row. A question suddenly appeared in her mind, ”From the L-th number to the R-th number, how many of them is a mutiple of P ? (P is a prime number) , and how quickly can I settle this problem ? ”

Input

Mutiple test cases. Please process till the end of file.
For each test case：
The first line contains two positive integers n and q (1<=n,q<=10^5), which means there are n integers standing in a row and q queries followed.
The second line contains n positive integers, a1,a2,a3,…,an (no more than 10^6) . Here, ai means the i-th integer in the row.
The next are q queries, each of which takes one line. For each query, there are three integers L,R,P (1<=L<=R<=n, 1<=P<=10^6, P is gurantteed to be a prime number). Their meanings have been mentioned in the discription.

Output

For each query, output the answer in one line.

Sample Input

6 5
12 8 17 15 90 28
1 4 3
2 6 5
1 1 2
3 5 17
1 6 999983

Sample Output

HINT

Source

題意：給出一個數組然後m個詢問，每次詢問l,r,p,詢問數組l~r區間內有幾個p的倍數
思路：首先打出素數表，然後對於數組每個數分解質因子，將相同的質因子作為下標，存包含這些質因子的那些數的坐標，然後可以直接查詢范圍

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define lson 2*i
#define rson 2*i+1
#define LS l,mid,lson
#define RS mid+1,r,rson
#define UP(i,x,y) for(i=x;i<=y;i++)
#define DOWN(i,x,y) for(i=x;i>=y;i--)
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define LL long long
#define N 1000000
#define INF 0x3f3f3f3f
#define EXP 1e-8
#define lowbit(x) (x&-x)
const int mod = 1e9+7;
vector prime[N+5];
bool vis[N+5];
int pos[N+5],tot;

void set()
{
    int i,j;
    memset(vis,1,sizeof(vis));
    for(i = 2; i<=N; i++)
    {
        if(vis[i])
        {
            if(N/i1)
                prime[pos[x]].push_back(i);
        }
        for(i = 1; iprime[y][len-1]||rr)
                R--;
            printf("%d\n",R-L+1);

        }
    }

    return 0;
}