HDU 6287 구 산 훈련 (유일 분해 정리 + 2 점)
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 512000/512000 K (Java/Others)Total Submission(s): 1400 Accepted Submission(s): 279
Problem Description
Q 군 은 수학 을 매우 좋아 하지만, 그의 말 솜 씨 는 매우 약 하 다.그래서 그 는 작은 T 를 찾 아 작은 T 에 게 길 이 를 주 었 다.
n 의 정수 시퀀스
a1, a2,..., an, 작은 T 던 져 달라 고 요구
m 개의 문 제 는 그의 계산 능력 을 훈련 시킨다.
각 문제 마다 세 개의 정수 를 제시 하 다
l, r, d, 작은 Q 는 암산 을 통 해 신속하게 판단 해 야 한다.
al×al+1×...×ar−1×옳 고 그 름
d 의 배수.
작은 Q 는 신속하게 대답 을 했 지만 작은 T 는 정 답 이 무엇 인지 모 르 니 작은 T 가 이 문제 들 의 정 답 을 계산 하 는 데 도움 을 주 는 프로그램 을 써 주세요.
Input
첫 줄 에는 정수 가 포함 되 어 있다.
T (1 ≤ T ≤ 10) 는 테스트 데이터 의 그룹 수 를 나타 낸다.
각 그룹의 데이터 첫 줄 에는 두 개의 정수 가 포함 되 어 있다.
n, m (1 ≤ n, m ≤ 100000) 는 각각 서열 길이 와 문제 개 수 를 나타 낸다.
두 번 째 줄 포함
n 개의 정수
a1, a2,..., an (1 ≤ ai ≤ 100000) 은 서열 중의 각 수 를 나타 낸다.
다음
줄 당 3 개의 정수
l, r, d (1 ≤ l ≤ r ≤ n, 1 ≤ d ≤ 100000) 는 모든 문 제 를 나타 낸다.
Output
모든 문제 에 대해 한 줄 을 출력 합 니 다. 배수 라면 Yes 를 출력 합 니 다. 그렇지 않 으 면 No 를 출력 합 니 다.
Sample Input
15 46 4 7 2 51 2 241 3 182 5 173 5 35
Sample Output
YesNoNoYes
题意：中文题目
思路：
1)运用：
1.vector (动态数组)
2.upper_bound (返回小于等于key的最后一个元素的后一个元素)
3.lower_bound (返回大于等于key的第一元素)
4.任何大于1的自然数，都可以唯一分解成有限个质数的乘积（唯一分解定理）
2）步骤：
1.将所给数组进行质因数分解，并且把数组标存入G[i]中。
//id原数组的下标，x原数组的值。eg：a[4]={2,3,4,5} prim(0,2)
void prim(int id,int x){
for(int i=2 ; i*i<=x ;i++){
while(x%i==0){
G[i].push_back(id);
x/=i;
}
}
if(x>1){
G[x].push_back(id);
}
}2. 조 회 된 P 도 질 인 수 를 분해 한 후 각 질 인수 의 개 수 를 원수 조 구간 에 대응 하 는 질 인수 의 개 수 를 비교한다
/*eg：
a b
30 6
2,3,5 2,3
36 6
2,2,3,3 2,3
只要b全部的质因数都出现在a中，且相应质因数小于等于a中的，
a就是b的倍数
*/3. 질 인 수 를 처리 할 때 (p 함수) 6/2 = 3 일 수 있 으 며, 이어서 3 은 처리 되 지 않 았 음 을 주의 하 십시오.
//质因数分解+二分答案
#include
using namespace std;
const int maxn = 1e5+10;
vector G[maxn];
//id原数组的下标，x原数组的值。eg：a[4]={2,3,4,5} prim(0,2)
void prim(int id,int x){
for(int i=2 ; i*i<=x ;i++){
while(x%i==0){
G[i].push_back(id);
x/=i;
}
}
if(x>1){
G[x].push_back(id);
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
for(int i=0;i1){
int pos = upper_bound(G[p].begin(),G[p].end(),r)-lower_bound(G[p].begin(),G[p].end(),l);
if(!pos){
flag=1;
}
}
if(flag) puts("No");
else puts("Yes");
}
}
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Dima and Lisa CodeForces - 584D텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
