CF1926D.Vlad and Division
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
The first line contains a single integer t ( 1≤t≤104 ) — the number of test cases.
The first line of each test case contains a single integer n ( 1≤n≤2⋅105 ) — the total number of integers.
The second line of each test case contains n given integers a1,…,an ( 0≤aj<231 ).
The sum of n over all test cases in a test does not exceed 2⋅105 .
输入格式
For each test case, output a single integer — the minimum number of groups required to satisfy the condition.
输出格式
In the first test case, any two numbers have the same last 31 bits, so we need to place each number in its own group.
In the second test case, a1=00000000000000000000000000000002 , a2=11111111111111111111111111111112 so they can be placed in the same group because a1(i)=a2(i) for each i between 1 and 31 , inclusive.
输入输出样例
输入#1
9 4 1 4 3 4 2 0 2147483647 5 476319172 261956880 2136179468 1671164475 1885526767 3 1335890506 811593141 1128223362 4 688873446 627404104 1520079543 1458610201 4 61545621 2085938026 1269342732 1430258575 4 0 0 2147483647 2147483647 3 0 0 2147483647 8 1858058912 289424735 1858058912 2024818580 1858058912 289424735 122665067 289424735
输出#1
4 1 3 2 2 3 2 2 4
说明/提示
In the first test case, any two numbers have the same last 31 bits, so we need to place each number in its own group.
In the second test case, a1=00000000000000000000000000000002 , a2=11111111111111111111111111111112 so they can be placed in the same group because a1(i)=a2(i) for each i between 1 and 31 , inclusive.