A-新春游戏之数学系列_“迎新春，过大年”多校程序设计竞赛

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Can you help Bingbong solve the math problem?

$Bingbong$ 的数学竞赛又考砸了，这也就意味着压岁钱又要减半了，但是！心地善良的朵朵姐姐决定再给他一次机会，给他出了一道数学题，如果他能正确解答，那么压岁钱就翻上一番。题目如下：

给你一个长度为 $n$ 的整数序列 $a_1,a_2,...,a_n$ 。

求： $\sum_{i=1}^n \sum_{j=1}^n gcd(a_i,a_j)\times (popcount(a_i)+popcount(a_j))$ % $998244353$

其中 $popcount(x)$ 表示整数 $x$ 在二进制下的 $1$ 的个数， $gcd$ 表示两个数的最大公约数。

$Bingbong$ 的由于竞赛考砸，心情还处于一个极其低落的状态，为了能拿到更多的压岁钱，他决定请教数学高手的你来帮助他解决这个问题。

第一行一个整数 。  第二行个整数，表示。
数据范围：

一行一个整数，表示答案。

示例1

复制

5
666 230 120 4 12

复制