trang chủ / đề bài / icpc25_nat_e

Định lý Fermat mở rộng

Đề bài

Mô tả

Trong lý thuyết số, Định lý lớn Fermat (đôi khi gọi là giả thuyết Fermat) khẳng định rằng không tồn tại ba số nguyên dương a, b và c thỏa mãn phương trình an+bn=cn với bất kỳ số nguyên n nào lớn hơn 2. Bài toán này đã không có lời giải trong suốt 358 năm, cho đến khi chứng minh thành công đầu tiên được Andrew Wiles công bố vào năm 1994.

Trong bài này, chúng ta sẽ giải một phiên bản mở rộng của Định lý lớn Fermat:

Cho một dãy gồm n+1 số nguyên tố đôi một khác nhau a1,a2,…,an,an+1 và một số nguyên p. Hãy tìm n+1 số nguyên dương x1,x2,…,xn,xn+1 sao cho:

  • xi<p,
  • ∑i=1nxiai≡xn+1an+1(modp).

Dữ liệu vào

Mỗi test gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu τ (1≤τ≤100). Tiếp theo là mô tả các bộ dữ liệu.

  • Dòng đầu tiên chứa hai số nguyên n và p (1≤n≤105, 109≤p≤1018).
  • Dòng thứ hai chứa n+1 số nguyên a1,a2,…,an,an+1 (1≤ai≤109).

Đảm bảo tổng n trên tất cả các bộ dữ liệu không vượt quá 105.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa n+1 số nguyên x1,x2,…,xn,xn+1 (0<xi<p). Nếu không có lời giải, in ra NO SOLUTION.

Nếu có nhiều lời giải, bạn có thể in ra bất kỳ lời giải nào.

Ràng buộc

  • 1≤τ≤100.
  • 1≤n≤105, tổng n không vượt quá 105.
  • 109≤p≤1018.
  • 1≤ai≤109, các ai là các số nguyên tố đôi một khác nhau.

Ví dụ

Input Output Giải thích
1
4 1000000009
3 5 7 11 2
1 1 1 1 2 13+15+17+111≡22(mod1000000009).
3
1 1000000007
2 3
2 1073741824
3 5 7
3 1000000000
2 11 13 5
1 1
214224833 565496962 994064801
1 999999999 1 1
Ví dụ bổ sung (không có trong đề gốc). Bộ 1: 12≡13. Bộ 2: 2142248333+5654969625≡57050977≡9940648017(mod230). Bộ 3: 12+99999999911+113≡1+(−1)+1=1≡15(mod109).

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