TLEoj Contest #08 - Ước chung lũy thừa

Điểm: 800 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

i_loveMaiPhuong

Dạng bài

Bạn được cho một dãy số $a$ dương gồm $n$ phần tử và một số nguyên dương $p$ . Nhiệm vụ của bạn là kiểm tra xem có cặp chỉ số $1\le i<j\le n$ thỏa mãn $gcd(p^{a_i}-1,p^{a_j}-1)=p^{gcd(a_i,a_j)}-1$ . Nếu có thì hãy xuất YES, ngược lại xuất NO.

Input, Output và Subtasks

Input: (bàn phím)

Dòng đầu tiên gồm 2 số nguyên dương $n,p$ ( $1\le n\le 10^5,1\le p\le 10^{18}$ ).
Dòng tiếp theo gồm $n$ số nguyên dương $a_1,a_2,\dots,a_n$ ( $1\le a_i\le 10^{18}$ ).

Output: (màn hình)

Nếu có cặp số thỏa mãn thì hãy xuất YES, ngược lại xuất NO.

Sample

Input (bàn phím)

2 3
1 2

Output (màn hình)

YES

Notes

Cặp số $(1,2)$ thỏa mãn vì $gcd(3^1-1,3^2-1)=gcd(2,8)=2$ và $3^{gcd(1,2)}-1=3-1=2$

Bình luận

Không có bình luận nào.