CaiWinDao và em gái thứ 4 (phần 2)

Xem PDF
Tác giả:
ami
Dạng bài
Điểm: 150 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Đây là phần tiếp theo của phần 1: https://lqdoj.edu.vn/problem/caiwinlau

CaiWinDao buồn vì em gái đã nhờ các bạn giải hộ bài toán trên (và ngủ sớm). Mà chẳng những vậy, các bạn còn giải trong vòng vài phút là xong. Lần này, anh quyết tâm rủ em gái ngủ lại một đêm nữa để phục thù.

Có thể bạn còn nhớ, trò chơi trong phần 1 như sau: "CaiWinDao lấy ra \(n\) đồng xu, sắp thành 1 hàng liên tiếp. Ban đầu tất cả đồng xu đều nằm ngửa. Mỗi lượt chơi, em gái có thể lật \(k\) đồng xu liên tiếp (úp thành ngửa và ngược lại). CaiWinDao đố em gái có thể lật úp tất cả đồng xu."

Lần này CaiWinDao chỉ thay thế đúng một chi tiết thôi nhưng chắc chắn sẽ làm em gái (và các bạn) thao thức. Thay vì sắp thành 1 hàng liên tiếp, anh sẽ sắp các đồng xu thành 1 vòng tròn, và luật chơi vẫn không thay đổi.

Em gái rất hoang mang, không biết CaiWinDao có ý đồ xấu gì không? Các bạn hãy giúp em gái xem thử với \(n, k\) cho trước, em gái có thể chiến thắng trò chơi và đi ngủ không nhé!

Input

  • Gồm 2 số nguyên \(n, k (1 \le k \le n \le 10^6)\).

Output

  • In ra YES nếu em gái có thể chiến thắng, NO nếu em gái không thể thắng (và thức trắng đêm).

Example

Test 2

Input 
3 2
Output 
NO

Test 3

Input 
4 2
Output 
YES

Test 4

Input 
4 3
Output 
YES

Test 5

Input 
14 12
Output 
NO

Bình luận


  • 10
    MinhSharingan    7:56 p.m. 1 Tháng 10, 2021 ← chỉnh sửa 4

    ** HINT 1 :** Có thể làm tất cả đồng xu cùng ngửa hoặc úp khi lật số lần bằng bội chung của n, k.

    ** HINT 2 :** Khi lật số lần bằng bội chung của n mà tất cả đồng xu ngửa thì trò chơi tiếp tục lặp lại vô hạn.

    ** HINT 3 :** Nếu lật hết x vòng thì * : *

    • Nếu x lẻ : Đồng xu không thể cùng ngửa
    • Nếu x chẵn : Đồng xu không thể cùng úp

    GNU C++ AC CODE:

    #include <iostream>
using namespace std;
long ucln(long a,long b)
{
    while (b!=0) {
        int mod=a % b;
        a=b;
        b=mod;
    } return a;
}
int main()
{
    long n,k;
    cin >> n >> k;
    long bcnn=(k*n)/ucln(n,k);
    if ((bcnn/n)%2!=0){
        cout << "YES";
      } else cout << "NO";
}
    4 phản hồi

    • 0
      minhkhoidepzai    10:44 a.m. 11 Tháng 9, 2021

      how to ac bài này vậy