trang chủ / đề bài / icpcwf21_c

Chia công bằng

Đề bài

Mô tả

Sau khi vượt qua Bảy Đại Dương và cướp bóc vô số con tàu, thuyền trưởng Red và các thủy thủ cướp biển của ông cuối cùng cũng sẵn sàng chia chiến lợi phẩm. Theo truyền thống cổ xưa, cả thủy thủ đoàn đứng thành một vòng tròn theo thứ bậc nghiêm ngặt của cướp biển. Thuyền trưởng Red bắt đầu bằng việc lấy một phần f của số chiến lợi phẩm rồi chuyển phần còn lại cho cướp biển kế tiếp. Người này lấy đúng phần f đó của số chiến lợi phẩm mà người trước để lại, rồi chuyển phần còn lại cho người tiếp theo. Mỗi cướp biển đều làm như vậy: lấy phần f của số đang có và chuyển phần còn lại đi. Cướp biển cuối cùng trong thứ bậc chuyển phần còn lại cho thuyền trưởng Red, người bắt đầu một vòng chia "công bằng" mới, và cứ thế mãi mãi.

May mắn là cướp biển thế kỷ 21 có thể dùng máy tính để tránh quá trình dài dòng này cùng những cuộc cãi vã không dứt mỗi khi phần f không chia hết số chiến lợi phẩm ở một bước nào đó. Bạn bị bọn cướp biển bắt và được yêu cầu tìm ra một tỉ lệ f phù hợp. Để khích lệ, thuyền trưởng Red hứa sẽ tha mạng cho bạn nếu bạn làm được.

Tỉ lệ f phải là một số hữu tỉ nằm thực sự giữa 0 và 1. Không bắt buộc f chia hết số chiến lợi phẩm còn lại ở bất kỳ bước nào của quá trình chia vòng tròn nói trên. Tuy nhiên, tổng số chiến lợi phẩm mà mỗi cướp biển nhận được khi thực hiện quá trình này vô hạn lần phải là một số nguyên.

Dữ liệu vào

Một dòng gồm hai số nguyên n và m, trong đó n (6≤n≤106) là số cướp biển (tính cả thuyền trưởng Red) và m (1≤m≤1018) là tổng giá trị chiến lợi phẩm.

Dữ liệu ra

In ra một dòng gồm hai số nguyên dương p và q sao cho f=p/q thỏa mãn yêu cầu trên. Nếu có nhiều tỉ lệ phù hợp, chọn tỉ lệ có q nhỏ nhất. Trong các tỉ lệ phù hợp có cùng q nhỏ nhất, chọn tỉ lệ có p nhỏ nhất. Nếu không có tỉ lệ nào phù hợp, in ra impossible và cầu mong được tha.

Ràng buộc

  • 6≤n≤106.
  • 1≤m≤1018.

Ví dụ

Input Output Giải thích
8 51000 1 2 Với f=1/2, cướp biển thứ i (i=1,…,8) nhận tổng cộng 51000·28−i/255=200·28−i, tức là 25600,12800,…,200: đều là số nguyên.
6 91000 2 3 f=1/2 không phù hợp. Với f=2/3, cướp biển thứ i nhận 91000·2·3−i/(1−3−6)=250·36−i, đều là số nguyên.
10 1000000000000000000 impossible Không có tỉ lệ nào phù hợp.

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