trang chủ / đề bài / icpc22_mb_b

Di chuyển

Đề bài

Mô tả

Bạn có một số m, một số bắt đầu s0 và hai dãy số ai và bi. Mục tiêu của bạn là đi từ s0 về 0 với số bước ít nhất. Ở mỗi bước, bạn chọn một chỉ số i, rồi nhân số hiện tại với ai, cộng thêm bi và lấy kết quả theo modulo m. Tức là

sj=(sj−1·aij+bij)modm.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên m, n và s0 (0<m≤1000000, 0≤n≤10, 0<s0<m).
  • n dòng tiếp theo, mỗi dòng chứa hai số nguyên ai và bi (0≤ai≤109, 0≤bi≤109).

Dữ liệu ra

In ra số bước ít nhất cần thiết để đi từ s0 về 0. Nếu không thể về 0 dù đi bao nhiêu bước, in ra −1.

Ràng buộc

  • 0<m≤1000000.
  • 0≤n≤10.
  • 0<s0<m.
  • 0≤ai,bi≤109.

Ví dụ

Input Output Giải thích
5 2 1
2 1
3 1
2 1→(1·2+1)mod5=3→(3·3+1)mod5=0. Không thể về 0 sau một bước vì 1·2+1=3 và 1·3+1=4.
6 2 1
1 2
5 0
-1 Cả hai phép biến đổi đều biến số lẻ thành số lẻ (với m=6 chẵn), nên từ 1 không bao giờ về được 0.

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