trang chủ / đề bài / icpc23_mt_c

Ước chung lớn nhất

Đề bài

Mô tả

Cho dãy số A gồm n số nguyên dương (1≤n≤100), số thứ i có giá trị ai (1≤ai≤70).

Xét tất cả các tập con khác rỗng của dãy A (hai phần tử ở hai vị trí khác nhau được coi là khác nhau, kể cả khi bằng giá trị), với mỗi tập con ta tính ước chung lớn nhất của các số trong tập. Hỏi tổng các ước chung lớn nhất của tất cả các tập con là bao nhiêu? Vì kết quả rất lớn, chỉ cần in ra phần dư của nó 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ộ dữ liệu. Tiếp theo là T bộ dữ liệu, mỗi bộ gồm:

  • Dòng đầu tiên chứa số nguyên dương n.
  • Dòng thứ hai chứa n số nguyên dương, số thứ i là ai.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa một số nguyên là đáp án của bộ dữ liệu đó.

Ràng buộc

  • 1≤T≤40
  • 1≤n≤100
  • 1≤ai≤70

Ví dụ

Input Output Giải thích
2
5
1 1 1 1 1
3
1 2 3
31
10
Bộ thứ nhất: mọi số đều bằng nhau nên mọi tập con có ước chung lớn nhất là 1; có 25−1=31 tập con khác rỗng nên tổng là 31. Bộ thứ hai: các tập con khác rỗng {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} có ước chung lớn nhất lần lượt là 1,2,3,1,1,1,1, tổng bằng 10.
2
3
4 6 70
1
70
88
70
Bộ thứ nhất: 4+6+70 cho ba tập một phần tử, mọi tập có từ hai phần tử trở lên có ước chung lớn nhất là 2, tổng 80+4·2=88. Bộ thứ hai chỉ có tập {70}.

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