hdu 6287 구 산 훈련 (이분 + 질 인수 분해 + 사유)

암산 훈련
Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 512000/512000 K (Java/Others) Total Submission(s): 1968    Accepted Submission(s): 423  
Problem Description
Q 군 은 수학 을 매우 좋아 하지만, 그의 말 솜 씨 는 매우 약 하 다.그래서 그 는 작은 T 를 찾 아 작은 T 에 게 길이 가 n 인 정수 서열 a1, a2, an 을 주 었 고 작은 T 에 게 m 개의 문 제 를 던 져 그의 계산 능력 을 훈련 시 켜 달라 고 요구 했다.각 문제 마다 3 개의 정수 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 행, 각 행 3 개 정수 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 중국 대학생 프로 그래 밍 경연 대회 - 여학생 특집
나 도 문 제 를 보고 한 거 야. 결국 수학 을 너무 못 하 는 거 야..
제목: 뻔 하 다.
사고: 여러 가지 사례 가 있 습 니 다. 각 조 는 m 개의 수, n 개의 요구 하 는 식 이 있 습 니 다. r 는 왼쪽 경계 이 고 l 은 오른쪽 경계 입 니 다. r 가 l 의 값 을 곱 하면 필요 한 수량 이 p 배수 입 니까?
1. 우 리 는 먼저 m 개 수 를 각각 질량 인 수 를 구하 고 G [i] 에 저장 할 수 있다. i 는 질량 인수 이 고 G [i] 는 아래 표 이다.
2. p 에 대해 질 인 수 를 구한다.
3. 포인트!!그 다음 에 물 어 보 는 수 분해 질량 인수 에 대해 모든 분해 에서 얻 은 질량 인 수 를 이 질량 인수 의 개수 가 같은 서열 에서 이 질량 인수 의 개수 보다 작 으 면 정리 할 수 있 고 그렇지 않 으 면 정리 할 수 없다.여기 서 2 분 검색 법 으로 서열 에서 질 적 인수 의 개 수 를 찾 습 니 다.
아직 잘 모 르 시 는 것 같은 데... 코드 를 올 려 주세요!!
이것 은 아주 잘 말 했 습 니 다. 상세 한 것 은 다음 과 같 습 니 다.https://blog.csdn.net/wjmwsgj/article/details/80519183

#include
#include
#include
#include
using namespace std;
vectorG[100001];
void fenjie(int id,int t)//    
{
	for(int i=2;i*i<=t;i++)
	{
		while(t%i==0)
		{
			G[i].push_back(id);//      ,G[x]     x   
			t=t/i;
		}
	}
	if(t>1)//  ！！
	{
		G[t].push_back(id);
	}
}
int main()
{
	int m,n,t,flag;
	int count;
	scanf("%d",&count);
	while(count--)
	{
		scanf("%d%d",&m,&n);
		for(int i=0;i<100001;i++)////    
		{
			G[i].clear();
		}
		for(int i=0;i1)//  ！！
			{
				int sum=upper_bound(G[p].begin(),G[p].end(),r)-lower_bound(G[p].begin(),G[p].end(),l);//    
				if(sum==0)
				{
					flag=0;
				}
			}
			if(flag==0)
			{
				printf("No
");
			}
			else
			{
				printf("Yes
");
			}
		}
	}
	return 0;
}