trang chủ / đề bài / icpcwf08_b

Luôn là số nguyên

Đề bài

Mô tả

Tổ hợp là một nhánh của toán học chủ yếu nghiên cứu việc đếm các đối tượng rời rạc. Chẳng hạn, có bao nhiêu cách chọn hai người từ một nhóm n người? Nối n điểm trên đường tròn với nhau thì chia hình tròn thành nhiều nhất bao nhiêu miền? Một kim tự tháp gồm các tầng hình vuông từ 1×1 đến n×n khối lập phương thì có bao nhiêu khối lập phương?

Hình 1: Nối sáu điểm trên đường tròn thì tạo ra nhiều nhất 31 miền.

Nhiều câu hỏi như vậy có đáp án quy về những đa thức đơn giản theo n. Đáp án của câu hỏi thứ nhất ở trên là n(n−1)/2, hay (n2−n)/2. Đáp án của câu hỏi thứ hai là (n4−6n3+23n2−18n+24)/24. Đáp án của câu hỏi thứ ba là n(n+1)(2n+1)/6, hay (2n3+3n2+n)/6. Ta viết các đa thức này ở dạng chuẩn: một đa thức hệ số nguyên chia cho một mẫu số nguyên dương.

Các đa thức này là đáp án của những câu hỏi chỉ có thể có đáp án nguyên. Nhưng vì chúng có hệ số phân số, trông chúng có vẻ như có thể cho kết quả không nguyên! Tất nhiên, tính giá trị của các đa thức cụ thể này tại một số nguyên dương luôn cho kết quả nguyên. Với các đa thức khác có dạng tương tự thì điều đó không nhất thiết đúng. Phân biệt hai trường hợp này có thể khó. Và đó, dĩ nhiên, là nhiệm vụ của bạn.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test, mỗi bộ test nằm trên một dòng riêng. Mỗi bộ test là một biểu thức dạng (P)/D, trong đó P là một đa thức với hệ số nguyên và D là một mẫu số nguyên dương. P là tổng của các hạng tử dạng CnE, trong đó hệ số C và số mũ E thỏa mãn các điều kiện sau:

  • E là số nguyên thỏa mãn 0≤E≤100. Nếu E=0 thì CnE được viết là C. Nếu E=1 thì CnE được viết là Cn, trừ khi C bằng 1 hoặc −1; khi đó CnE được viết là n hoặc -n.
  • C là số nguyên. Nếu C bằng 1 hoặc −1 và E khác 0 và 1 thì CnE được viết là n^E hoặc -n^E.
  • Chỉ các giá trị C không âm không thuộc hạng tử đầu tiên của đa thức mới có dấu + đứng trước.
  • Số mũ của các hạng tử liên tiếp giảm ngặt.
  • C và D vừa với kiểu số nguyên có dấu 32 bit.

Xem ví dụ để biết thêm chi tiết. Dữ liệu kết thúc bằng một dòng chỉ chứa một dấu chấm ..

Dữ liệu ra

Với mỗi bộ test, in số thứ tự bộ test (bắt đầu từ 1). Sau đó in Always an integer nếu đa thức của bộ test cho giá trị nguyên tại mọi số nguyên dương n, ngược lại in Not always an integer. Kết quả của các bộ test in trên các dòng riêng. Định dạng theo đúng ví dụ.

Ràng buộc

  • 0≤E≤100, −231≤C≤231−1, 1≤D≤231−1.
  • Các dòng không chứa dấu cách.
  • Mỗi file có không quá 200 bộ test.

Ví dụ

Input Output Giải thích
(n^2-n)/2
(2n^3+3n^2+n)/6
(-n^14-11n+1)/3
.
Case 1: Always an integer
Case 2: Always an integer
Case 3: Not always an integer
Bộ 3: với n=1, giá trị là (−1−11+1)/3=−11/3, không nguyên.
(n^5-n)/30
(n^3+2n)/3
(n^2-3n+2)/4
(7)/7
(n)/1
.
Case 1: Always an integer
Case 2: Always an integer
Case 3: Not always an integer
Case 4: Always an integer
Case 5: Always an integer
Bộ 2: n3+2n=(n−1)n(n+1)+3n luôn chia hết cho 3. Bộ 3: giá trị bằng 0 tại n=1 và n=2 nhưng bằng 2/4 tại n=3.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0