题解 | #新春游戏之数学系列#

A

关注点放在序列中出现不同个数最多会有多少个

题干中关键信息

显然会发现 1 、 2 、 3 、 4 、…… 、k

( + )/2

预处理出不同元素及个数暴力统计贡献就好

#include <bits/stdc++.h>

using namespace std ;

using i64 = long long ;
const int p = 998244353 ;
const int N = 1e6 + 10 ; 

int n ; 

int gcd(int a,int b) {
	return b ? gcd(b , a  % b) : a ;
}

void solve()
{
	cin >> n ;
    unordered_map<i64 , i64> mp ;
	for(int i = 1 ; i <= n ; i++) {
        int x ; 
        cin >> x ;
        ++mp[x] ; 
    }
	i64 ret = 0 ;
    for(auto a : mp)
    {
        for(auto b : mp)
        {
        	ret = (ret + a.second * b.second * gcd(a.first , b.first) % p * (__builtin_popcount(a.first) + __builtin_popcount(b.first) ) % p) % p;
        }
    }
    
    cout << ret ; 
}

int main()
{
	ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;

	int t = 1 ;
	// cin >> t ;

	while (t--)
	{
		solve() ; 
	}
	return 0 ; 
}