구 산 훈련 (hdu 6287) (유일 분해 정리)

암산 훈련
Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 512000/512000 K (Java/Others) Total Submission(s): 1963    Accepted Submission(s): 419
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 중국 대학생 프로 그래 밍 경연 대회 - 여학생 특집
배수 와 관련 된 것 은 인 자 를 연상 시 켜 야 한다. 그렇지 않 으 면 시간 을 초과 할 수 있 고 인자 수 는 매우 적다. 유일한 분해 정 리 를 이용 하여 소 인자 의 개 수 를 구하 고 다시 2 분 동안 찾 아 [l, r] 가 소 인자 수 를 완전히 덮 을 수 있 는 지 판단 해 야 한다.

#include
using namespace std;
const int maxn=1e+5;
vectorG[maxn];
bool check(int l,int r,int d)
{
    int ans;
    for(int j=2; j*j<=d; j++)
    {
        if(d%j==0)
        {
            int cnt=0;
            while(d%j==0)
                cnt++,d/=j;
            ans=upper_bound(G[j].begin(),G[j].end(),r)-lower_bound(G[j].begin(),G[j].end(),l);
            if(cnt>ans) return false;
        }
    }
    if(d>1)
    {
        ans=upper_bound(G[d].begin(),G[d].end(),r)-lower_bound(G[d].begin(),G[d].end(),l);
        if(ans<1) return false;
    }
    return true;
}
int main()
{
    int t,n,m,l,r,d,x;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=maxn;i++) G[i].clear();
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&x);
            for(int j=2; j*j<=x; j++)
            {
                while(x%j==0)
                {
                    G[j].push_back(i);
                    x/=j;
                }
            }
            if(x>1)
                G[x].push_back(i);
        }
        while(m--)
        {
            scanf("%d%d%d",&l,&r,&d);
            bool flag=check(l,r,d);
            printf("%s
",flag?"Yes":"No");
        }
    }
}