For Primary Students

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

0

mapubzz 8:58 p.m. 23 Tháng 5, 2024

Sao bài này dùng python lại bị TLE . Đoạn code của mình :

t = int(input().strip())
for i in range(t):
k = int(input().strip())
if k > 1:
print(k - 1)
elif k == 1:
print(-1)

Các cao nhân giải thích lý do TLE giúp .

bạn có thể dùng 1 số kĩ thuật với các thư viện để tối ưu thời gian chạy code với python nha :>

import sys
t = int(sys.stdin.readline())
res = []
for i in range(t):
    k = int(sys.stdin.readline())
    res.append(str(k - 1) if k > 1 else str(-1))
sys.stdout.write('\n'.join(res) + '\n')

0

dang7rickroll 10:49 p.m. 23 Tháng 5, 2024

tại vì bạn xài python bạn có thể xài c++ để giảm thời gian

0

Vodangngoclam 5:22 p.m. 17 Tháng 7, 2024

pypy thử

1

doanngocgiahung2013 3:14 p.m. 9 Tháng 7, 2024

nhưng nếu chưa học c++ thì sao anh ? làm cách nào ac đc

5 bình luận nữa