For Primary Students

Xem PDF



Tác giả:
Dạng bài
Ngôn ngữ cho phép
C++, Clang, Clang++, Cobol, D, Groovy, Haskell, JS, Lua, Node JS, ObjectiveC, Output, Pascal, Prolog, Python, Scala, Scratch
Điểm: 800 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Một bài toán cực đơn giản cho HS tiểu học.

Cho một số nguyên dương \(k\).

Nhiệm vụ của bạn là tìm số nguyên dương \(x\) lớn nhất thỏa mãn \(1 \le x < k\) sao cho \(x! + (x-1)!^\dagger\) chia hết cho \(k\).

\(^\dagger\) \(y!\) được định nghĩa như sau: \(y!=1\times 2 \times 3 \times \ldots \times y\). Tuy nhiên, hãy lưu ý rằng \(0!=1\). Ví dụ \(5!=5\times 4 \times 3 \times 2 \times 1=120\).

Input

  • Dòng thứ nhất chứa \(t\) \((t \leq 10^6)\) - số câu hỏi.
  • \(t\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(k\) \((k \leq 10^{18})\).

Output

  • Ứng với mỗi câu hỏi in ra đáp án thỏa mãn. Nếu không có \(x\) nào thỏa mãn, in ra \(\texttt{-1}\).

Scoring

  • 30% test có \(t \le 100\);
  • 70% test còn lại: không ràng buộc gì thêm.
  • Lưu ý: Chia subtask cho mục đích giải trí, bạn không thể cày trâu bài này được đâu ahihi

Example

Test 1

Input
2
2
1
Output
1
-1
Giải thích

\(1!+0!=2\) chia hết cho \(2\) (\(2 \div 2 = 1\))


Bình luận


  • 1
    hbphuc2009    10:12 a.m. 8 Tháng 1, 2023

    :v bài này là Problem A trong contest Div 1, cơ mà ko bt cách làm:((


    • 1
      Toilaaibanbietko7A4    10:47 a.m. 10 Tháng 1, 2023

      Bài này đơn giản mà :V Đáp án cho mỗi giá trị \(k\) chính là \(k - 1\).
      Giải thích (siêu đơn giản): \((k - 1)! + (k - 2)!\) = \((k - 2)! * ((k - 1) + 1)\) = \((k - 2)! * k \equiv 0\) \((\text{mod}\) \(k)\)


      • 1
        hbphuc2009    2:36 p.m. 10 Tháng 1, 2023

        sao mình lại TLE 2 test nhỉ?


        • 1
          hbphuc2009    2:26 p.m. 10 Tháng 1, 2023

          =(( ngu toán thì chịu thôi:)

        5 bình luận nữa