Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>/*{{{*/
- using namespace std;typedef long long ll;typedef long double ld;void run();int main(){ios::sync_with_stdio(0);run();}/*}}}*/
- set<int> prime_factors(int n){
- set<int> res;
- for (int i=2; i*i<=n; i++){
- if (n%i==0){
- res.insert(i);
- while (n%i==0) n/=i;
- }
- }
- if (n>1) res.insert(n);
- return res;
- }
- bool is_prime(int n){
- for (int i=2; i*i<=n; i++) if (n%i==0) return false;
- return true;
- }
- int gcd(int a,int b){return b?gcd(b,a%b):a;}
- void run(){
- int tsts; cin>>tsts; for (int tst=1; tst<=tsts; ++tst){
- cerr<<"running test "<<tst<<" of "<<tsts<<endl;
- int n,k; cin>>n>>k;
- vector<int> val(n); for (auto &i: val) cin>>i; sort(val.rbegin(),val.rend());
- if (val.back()==0) val.pop_back(), --n;
- sort(val.begin(),val.end());
- int sof[50]={};
- for (int i=0; i<n; i++) sof[i+1]=sof[i]+val[i];
- int agn[50]={};
- int best=0;
- for (int i=0,j=1; i<n; i++){
- if (val[i]>1){
- do j++; while (j*k<val[i] or not is_prime(j));
- }
- best+=j*k-val[i];
- agn[i]=j;
- }
- for (int aug=1; aug--;){
- for (int i=n; i--;){
- for (int j=max(1,(val[i]+k-1)/k); j<agn[i]; j++){
- bool ok=true;
- for (int k=n; k--;) if (k!=i and gcd(agn[k],j)>1) {ok=false;break;}
- if (ok){
- best+=k*(j-agn[i]);
- agn[i]=j;
- aug=1;
- break;
- }
- }
- }
- sort(agn,agn+n);
- }
- map<vector<int>,int> dp[30];
- dp[0][vector<int>()]=0;
- vector<int> pf[1000];
- for (int i=1; i<=500; i++){
- set<int> pfs=prime_factors(i);
- for (auto j: pfs) pf[i].push_back(j);
- }
- for (int i=0; i<n; i++){
- for (int x=max(1,(val[i]+k-1)/k); x<=500; x++){
- for (pair<vector<int>,int> const &j: dp[i]){
- if (j.second+x*k*(n-i)-(sof[n]-sof[i])>=best) continue;
- int cost=j.second+x*k-val[i];
- bool ok=true;
- for (auto q: pf[x]) if (binary_search(j.first.begin(),j.first.end(),q)) {ok=false;break;}
- if (not ok) continue;
- vector<int> all=j.first;
- for (auto q: pf[x]) all.push_back(q);
- sort(all.begin(),all.end());
- if (not dp[i+1].count(all) or dp[i+1][all]>cost) dp[i+1][all]=cost;
- }
- }
- }
- int res=best;
- for (auto i: dp[n]) res=min(res,i.second);
- if (res==best) cerr<<" answer = bruteforce"<<endl;
- cout<<"Case #"<<tst<<": "<<res<<endl;
- }
- cerr<<"finished"<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement