题解：P13027 [GCJ 2021 #1A] Prime Time

· · 题解

一道有点思维的难度的题，但是想到了还是很好做的。

题目传送门

题意简述

把一些质数分成两组，使第一组的和等于第二组的积，一种分法的得分为第一组的和（也就是第二组的积），输出最大的得分。

暴力思路

爆搜这里就不讲了吧。

注意到数字全是质数，和质数有关的是什么？质因数分解！对于每一个数，都可以把它分解为若干个质数的积的形式，并且分解方法是唯一的。

于是我们就有了一个暴力思路：从大到小枚举得分，然后遍历卡牌，如果得分能整除当前的卡牌就除掉，最后判断得分能否除到 1，剩下的卡牌之和是否等于得分。如果前面两个条件都满足，这就是一种合法的方案。

一个小优化

现在得分的范围太大了，范围足足从 1 到 \sum_{i=1}^M P_i \times N_i，显然是无法接受的，那么能不能缩小一下得分的范围？

办法是有的。由于质数最小是 2，想要让得分到 10^{15}，最多只要 60 个数就足够了（2^{60} 已经大大超过了 10^{15}），也就是被选到第二组的数字不会超过 60 个。

得出这个结论，这道题就很好做了。被选到第二组数字的和不会超过 60 \times 499，那么第一组的数字和最小只有 \sum_{i=1}^M P_i \times N_i-60 \times 499。得分的范围已经大大缩小了。

最后提醒大家两句话：

多测不清空，爆零两行泪。

十年 OI 一场空，不开 long long 见祖宗。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll T,m,p[105],n[105];
int main(){
    cin>>T;
    for(ll t=1;t<=T;t++){
        cin>>m;
        ll sum=0,ans=0,cnt=0;
        for(ll i=1;i<=m;++i){
            cin>>p[i]>>n[i];
            sum+=p[i]*n[i];//所有计算数字总和
        }
        for(ll i=sum;i>=max((ll)2,sum-499*60);i--){
            ll x=i,f=0,sum1=0;
            for(ll j=1;j<=m;++j)
                for(int k=1;k<=n[j]&&x%p[j]==0;k++){
                    x/=p[j];//能除的全都除掉
                    sum1+=p[j];//计算第二组数字的和
                }
            if(x>1)continue;//得分不能除完就不是合法方案
            if(sum-sum1==i){//这是合法的情况
                ans=i;
                break;
            }
        }
        cout<<"Case #"<<t<<": "<<ans<<'\n';
    }
    return 0;
}