trang chủ / đề bài / icpc24_mt_c

Tổng các BCNN

Đề bài

Mô tả

Cho dãy A gồm N số nguyên dương.

Xét tất cả các tập con khác rỗng của dãy A và tính bội chung nhỏ nhất (BCNN, tiếng Anh: LCM) của các phần tử trong mỗi tập con. Hãy tính tổng tất cả các giá trị BCNN đó.

Hai tập con được coi là khác nhau nếu chúng chọn các tập vị trí khác nhau (các phần tử bằng nhau ở các vị trí khác nhau vẫn được tính riêng). Vì kết quả có thể rất lớn, hãy in ra phần dư của tổng khi chia cho 109+7.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên dương T (1≤T≤40): số bộ test.
  • Mỗi bộ test gồm:
    • một dòng chứa số nguyên dương N (1≤N≤100);
    • tiếp theo là N số nguyên dương A[1],A[2],…,A[N] (1≤A[i]≤500), cách nhau bởi dấu cách hoặc xuống dòng.

Dữ liệu ra

In ra T dòng, mỗi dòng chứa một số nguyên: đáp án của bộ test tương ứng.

Ràng buộc

  • 1≤T≤40
  • 1≤N≤100
  • 1≤A[i]≤500

Ví dụ

Input Output Giải thích
4
5
1 1 1 1 1
3
1 2 3
6
4 4 4 2 2 2
10
9 5 12 58 1 85 24 90 100 99
31
23
238
651657343
Ví dụ của đề gốc. Bộ test thứ nhất có 25−1=31 tập con khác rỗng, mỗi tập có BCNN bằng 1. Bộ test thứ hai: 1+2+3+2+3+6+6=23.
3
1
6
2
23 46
2
256 3
6
115
1027
Ví dụ bổ sung, tính bằng lời giải mẫu. Bộ test thứ hai: 23+46+46=115. Bộ test thứ ba: 256+3+768=1027.

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