trang chủ / đề bài / tst23_gcdlcm

Sinh test GCD/LCM

Đề bài

Mô tả

Nam được giao nhiệm vụ sinh test cho bài toán sau:

Cho một dãy A gồm n số nguyên dương. Gọi A0 là dãy A trước khi thực hiện các truy vấn.

Thực hiện q truy vấn thuộc một trong ba dạng như sau:

  • "GCD l r v x": A[i]=gcd(A[i],vx) với mọi l≤i≤r.
  • "LCM l r v x": A[i]=lcm(A[i],vx) với mọi l≤i≤r.
  • "CHK l r": Cho biết với mọi i trong đoạn [l,r] thì A0[i]=A[i] hay không?

Để sinh một bộ test tốt, với mỗi truy vấn loại 3, Nam cần biết có bao nhiêu cách điền giá trị vào A[l],A[l+1],…,A[r] sao cho thỏa mãn điều kiện đã cho.

Hãy giúp Nam giải quyết bài toán mới này.

Dữ liệu vào

  • Dòng đầu chứa hai số nguyên dương n, q (1≤n,q≤105) tương ứng với độ dài dãy A và số truy vấn.
  • Mỗi dòng trong q dòng tiếp theo chứa một truy vấn như trên đề bài (1≤l≤r≤n, 2≤v≤107, 1≤x≤107).

Dữ liệu ra

Với mỗi truy vấn loại 3, gọi ans là số bộ giá trị có thể điền vào A[l],A[l+1],…,A[r] sao cho thỏa điều kiện của truy vấn. Nếu ans≤9×1018 thì in ans, ngược lại in −1. Mỗi kết quả in trên một dòng.

Ràng buộc

  • 1≤n,q≤105.
  • 1≤l≤r≤n, 2≤v≤107, 1≤x≤107.

Subtasks

  • Subtask 1 (12 điểm): n,q≤2000, v≤20, x≤2.
  • Subtask 2 (14 điểm): Không có truy vấn loại 2, x≤2.
  • Subtask 3 (16 điểm): Không có truy vấn loại 2.
  • Subtask 4 (19 điểm): n,q≤2000.
  • Subtask 5 (21 điểm): v≤20.
  • Subtask 6 (18 điểm): Không có giới hạn gì thêm.

Ví dụ

Input Output Giải thích
5 6
CHK 2 4
LCM 1 1 10 1
GCD 1 3 9 1
GCD 1 5 9 5
CHK 1 3
CHK 1 5
-1
27
3267
Truy vấn CHK đầu tiên: chưa có thao tác nào nên mọi giá trị đều thỏa mãn, có vô số cách, in −1. Truy vấn CHK thứ hai: mỗi A[i] với 1≤i≤3 phải thuộc {1,3,9}, có 33=27 cách. Truy vấn CHK thứ ba: thêm A[4],A[5] là ước của 95=310, mỗi số có 11 cách, tổng cộng 27·121=3267.
4 7
GCD 1 4 12 1
CHK 1 4
LCM 2 3 2 1
GCD 4 4 2 3
CHK 1 4
LCM 1 1 3 1
CHK 1 2
1296
288
12
Ví dụ bổ sung (không có trên VNOJ). Lúc đầu mỗi A[i] phải là ước của 12: 6 cách, 64=1296. Sau đó A[2],A[3] phải là ước của 12 chia hết cho 2 (4 cách), A[4]∈{1,2,4} (3 cách): 6·4·4·3=288. Cuối cùng A[1] phải là ước của 12 chia hết cho 3 (3 cách): 3·4=12.

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