trang chủ / đề bài / icpc23_mt_b

Câu lạc bộ Ocean

Đề bài

Mô tả

Bi rất thích loạt phim Ocean trên kênh HBO. Vì quá yêu thích, Bi đã lập một câu lạc bộ Ocean của riêng mình trong lớp. Để luyện kỹ năng giống các nhân vật trong phim, Bi đưa ra một bài toán cho các thành viên luyện tập như sau.

Câu lạc bộ Ocean của Bi có n thành viên, số nhà của họ lần lượt là A={a1,a2,…,an} (các số đôi một khác nhau). Quy tắc liên lạc của câu lạc bộ là: thành viên ở nhà số x có thể chuyển tin trực tiếp cho thành viên ở nhà số y khi và chỉ khi x<y và x, y nguyên tố cùng nhau (gcd(x,y)=1).

Bi yêu cầu các thành viên tính nhanh: để chuyển tin từ nhà số ai tới nhà số aj sao cho tin đi qua đúng k+1 người (tính cả người gửi ở nhà ai và người nhận ở nhà aj), tức là tin được chuyển trực tiếp đúng k lần, thì có bao nhiêu cách?

Các thành viên câu lạc bộ chưa giỏi việc này, nên Bi nhờ bạn tính giúp.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên n (1≤n≤100): số thành viên.
  • Dòng thứ hai chứa n số nguyên đôi một khác nhau a1,a2,…,an (2≤ai≤105): danh sách số nhà.
  • Dòng thứ ba chứa số nguyên Q (1≤Q≤105): số câu hỏi Bi đưa ra.
  • Q dòng tiếp theo, mỗi dòng chứa ba số nguyên ai,aj,k (ai≤aj; ai,aj∈A; 1≤k≤n).

Dữ liệu ra

In ra Q dòng, dòng thứ i là đáp án của câu hỏi thứ i. Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho 2023.

Ràng buộc

  • 1≤n≤100, 2≤ai≤105, các ai đôi một khác nhau
  • 1≤Q≤105
  • ai≤aj; ai,aj∈A; 1≤k≤n

Ví dụ

Input Output Giải thích
7
2 3 4 5 6 7 8
1
2 8 3
3 Có 3 cách chuyển tin từ nhà 2 tới nhà 8 qua đúng 4 người: 2→3→5→8, 2→3→7→8 và 2→5→7→8.
4
9 2 5 4
4
2 9 1
2 9 2
2 2 1
4 9 1
1
1
0
1
Các cách: 2→9 (một lần chuyển); 2→5→9 (hai lần chuyển). Không thể chuyển từ nhà 2 tới chính nó. Từ nhà 4 tới nhà 9 có cách 4→9.

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