만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

Integral Array

시간 제한2초메모리 제한1024 MB

요약
배열에서 고른 모든 x, y (x ≥ y) 쌍에 대해 floor(x/y)가 배열에 있는지 확인합니다. 배열의 값은 c 이하입니다.
난이도

보통10점 중 5점

유형
누적 합, 수학
정답자
아직 제출이 없습니다

문제

양의 정수 nn개로 이루어진 배열 aa가 주어진다. 배열의 임의의 두 수 xx, yy (같은 원소를 가리킬 수도 있다)에 대해 x≥yx \ge y이면 ⌊xy⌋\left \lfloor \frac{x}{y} \right \rfloor (xx를 yy로 나눈 몫을 내림한 값)도 배열에 있을 때, 이 배열을 integral이라고 한다. aa의 모든 수는 cc를 넘지 않는다. 배열이 integral인지 확인하라.

입력

첫 줄에 테스트 케이스의 수 tt (1≤t≤10 0001 \le t \le 10\,000)가 주어진다. 각 테스트 케이스의 첫 줄에는 nn과 cc (1≤n≤1061 \le n \le 10^6, 1≤c≤1071 \le c \le 10^7)가 주어진다. 둘째 줄에는 a1,a2,…,ana_1, a_2, \ldots, a_n (1≤ai≤c1 \le a_i \le c)이 주어진다. 모든 테스트 케이스에 대한 nn의 합을 NN, cc의 합을 CC라 하면 N≤106N \le 10^6, C≤107C \le 10^7이다.

출력

각 테스트 케이스마다 배열이 integral이면 Yes, 아니면 No를 출력한다.

힌트

첫 번째 테스트 케이스에서 배열은 integral이다. 예를 들어 ⌊52⌋=2\left \lfloor \frac{5}{2} \right \rfloor = 2이고 2는 배열에 있다. 두 번째 테스트 케이스에서는 ⌊73⌋=2\left \lfloor \frac{7}{3} \right \rfloor = 2인데 2가 배열에 없으므로 integral이 아니다. 세 번째 테스트 케이스에서는 ⌊22⌋=1\left \lfloor \frac{2}{2} \right \rfloor = 1인데 배열에는 2만 있으므로 integral이 아니다.

예제1

  1. 예제 1

    입력
    3
    3 5
    1 2 5
    4 10
    1 3 3 7
    1 2
    2
    
    예상 출력
    Yes
    No
    No