訓練賽二 hdu 6287（質因數分解+區間查找+二分優化）

口算訓練

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 512000/512000 K (Java/Others)

Total Submission(s): 2252    Accepted Submission(s): 500

Problem Description

小Q非常喜歡數學，但是他的口算能力非常弱。是以他找到了小T，給了小T一個長度為n的正整數序列a1,a2,...,an，要求小T抛出m個問題以訓練他的口算能力。

每個問題給出三個正整數l,r,d，小Q需要通過口算快速判斷al×al+1×...×ar−1×ar是不是d的倍數。

小Q迅速地回答了出來，但是小T并不知道正确答案是什麼，請寫一個程式幫助小T計算這些問題的正确答案。

Input

第一行包含一個正整數T(1≤T≤10)，表示測試資料的組數。

每組資料第一行包含兩個正整數n,m(1≤n,m≤100000)，分别表示序列長度以及問題個數。

第二行包含n個正整數a1,a2,...,an(1≤ai≤100000)，表示序列中的每個數。

接下來m行，每行三個正整數l,r,d(1≤l≤r≤n,1≤d≤100000)，表示每個問題。

Output

對于每個問題輸出一行，若是倍數，輸出Yes，否則輸出No。

Sample Input

1 5 4 6 4 7 2 5 1 2 24 1 3 18 2 5 17 3 5 35

Sample Output

Yes No No Yes

Source

"位元組跳動杯"2018中國大學生程式設計競賽-女生專場

Recommend

liuyiding   |   We have carefully selected several similar problems for you:  6447 6446 6445 6444 6443 

Statistic | Submit | Discuss | Note

心得：一開始想用線段樹做，但逾時了，後來想到分解數字，但沒辦法查詢。

1、對輸入的數進行分解，并用數組存儲，由于數的最大值已經确定，可以用分解的質因數對應下标來存儲；

2、要查詢一個數時，先分解這個數，然後在L和R這個區間查詢，可以用upper_bound()-lower_bound()來優化

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 2e5+10;
vector <int> vc[maxn];
void it(int x,int p)
{
	int tp=p;
	for(int i=2;i*i<=tp;i++)
	{
		while(tp%i==0)
		{
			vc[i].push_back(x);
			tp/=i;
		}
	}
	if(tp>1) vc[tp].push_back(x);
}
int fd(int l,int r,int x)
{
	return upper_bound(vc[x].begin(),vc[x].end(),r)-lower_bound(vc[x].begin(),vc[x].end(),l);
}
int main(void)
{
	int t,i,l,r,d,p;
	int n,m,j;
	scanf("%d",&t);
	while(t--)
	{
		for(i=0;i<maxn;i++) vc[i].clear();
		scanf("%d %d",&n,&m);
		for(i=1;i<=n;i++)
		{
			scanf("%d",&p);
			it(i,p);
		}
		for(i=1;i<=m;i++)
		{
			scanf("%d %d %d",&l,&r,&d);
			int fg=0,cnt;
			for(j=2;j*j<=d;j++)
			{
				cnt=0;
				while(d%j==0)
				{
					cnt++;
					d/=j;
				}
				if(cnt>fd(l,r,j)) 
				{
					fg=1;break;
				}
			}
			if(d>1&&fd(l,r,d)==0&&fg==0) fg=1;
			if(fg==0) printf("Yes\n");
			else printf("No\n");
		}
	}
	return 0; 
}
           

參考文章：https://blog.csdn.net/ZscDst/article/details/80497236