题解：CF2200H Six Seven

MaxBlazeResFire · 2026-03-04 12:13:59 · 题解

当 42\nmid x 时，x 合法当且仅当 x\bmod 42 是 6 的倍数。否则 x 合法当且仅当 \displaystyle\frac{x}{42} 是合法的。运用了 f_6(x),f_7(x) 同时减一的特性。

枚举答案 m 模 42 的余数 k。先用前者判据判掉一些必然不合法的 k。不难发现，对于一个 k，我们拿出所有能被整除 42 的 a_i+k，把它们除掉 42 后得到序列 b，求解 b 的答案 m'，不难发现 42m'+k 就是 m 的答案。注意到 n 个数均摊在 k 种情况，于是分治树上每一层都是 n 个数。

复杂度 O(n\log_{42}V)，有一个 42 的常数。

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define MAXN 200005
#define INF (int)2e18
int n,a[MAXN];

//求解集合 A 的答案
int solve( vector<int> A ){
    if( !(int)A.size() ) return 0;
    int maxx = 0;
    for( int ele : A ) maxx = max( maxx , ele );
    if( maxx < 2 ) return 5;
    vector<int> P[42];  
    for( int ele : A ) P[ele % 42].emplace_back( ele );
    int res = INF;
    for( int k = 0 ; k < 42 ; k ++ ){
        //钦定余数 k。此时不允许存在 a[i] + k mod 42 不为 6 的倍数的情况
        bool flag = 1;
        for( int j = 0 ; j < 42 ; j ++ )
            if( (int)P[j].size() && ( j + k ) % 6 ){ flag = 0; break; }
        if( !flag ) continue;
        int t = ( 42 - k ) % 42;
        vector<int> tmp;
        for( int ele : P[t] ) tmp.emplace_back( ( ele + k ) / 42 );
        int r = solve( tmp );
        if( r != -1 ) res = min( res , solve( tmp ) * 42 + k );
    }
    if( res == INF ) res = -1;
    return res;
}

inline void solve(){
    scanf("%lld",&n);
    vector<int> A;
    for( int i = 1 ; i <= n ; i ++ ) scanf("%lld",&a[i]),A.emplace_back( a[i] );
    printf("%lld\n",solve( A ));
}

signed main(){
    int t; scanf("%lld",&t);
    while( t -- ) solve();
    return 0;
}