Submission #631305

#	Time	Username	Problem	Language	Result	Execution time	Memory
631305		socpite	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	959 ms	155720 KiB

brunhilda

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

#define f first
#define s second

const int mx = 1e7+5;
const int maxn = 1e5+5;

typedef long long ll;

ll lim = 1;

int m, q, ans;

int dp[mx], cnt[mx], pp[mx], mm[mx];
vector<int> primes;
int l = 0, r = 0;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> m >> q;
    for(int i = 2; i < mx; i++){
        if(!pp[i]){
            pp[i]=i;
            primes.push_back(i);
        }
        for(auto v: primes){
            if(i*v >= mx)break;
            pp[i*v]=v;
            if(i%v==0)break;
        }
    }
    while(m--){
        int x;
        cin >> x;
        if(!mm[x]){
            lim*=x;
            if(lim >= mx)lim = mx;
            cnt[0]++;
        }
        mm[x] = 1;
    }
    for(int i = 1; i < lim; i++){
        int tmp = i;
        while(pp[tmp]){
            int prv = pp[tmp];
            while(pp[tmp] == prv){
                tmp/=prv;
            }
            if(mm[prv]){
                cnt[i-prv]--;
                cnt[i]++;
            }
        }
        while(!cnt[r])r++;
        dp[i]=dp[r]+1;
    }
    while(q--){
        int x;
        cin >> x;
        if(x >= lim)cout << "oo";
        else cout << dp[x];
        cout << "\n";
    }


}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 60 / 60