1005: 青春异或少女不会遇到lcm学长

Memory Limit:256 MB Time Limit:4.000 S
Judge Style:Text Compare Creator:
Submit:157 Solved:39

Description

给定一个数组$a$,求: $$\sum_{i=1}^{n}\sum_{j=i}^{n}{(a_i \oplus a_j) \times lcm(a_i, a_j)}$$ 结果对$10^9 + 7$取模。 $\oplus$表示异或运算,$lcm(a, b)$表示$a, b$的最小公倍数。 ### 输入格式 第一行两个整数$n$表示数组长度。$(1\le n \le 2 \times 10^5)$ 第二行$n$个整数,第$i$个整数表示$a_i$。$(0 \le a_i \le 2 \times 10^3)$ ### 输出格式 一个数字,表示取模后的结果。 ### 输入样例 ``` 3 1 2 3 ``` ### 输出样例 ``` 18 ``` ### 提示 样例中$(1 \oplus 2) \times lcm(1, 2) + (1 \oplus 3) \times lcm(1, 3) + (2\oplus3) \times lcm(2, 3) = 3 \times 2 + 2 \times 3 + 1 \times 6 = 18$。