Submission #631300

#	Time	Username	Problem	Language	Result	Execution time	Memory
631300		socpite	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	50.95 / 100	1107 ms	262144 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], pp[mx], mm[mx];
vector<int> primes;
int l = 0, r = 0;
pair<int, int> que[maxn*130];

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;
            que[r++]={0, x};
        }
        mm[x] = 1;
    }
    for(int i = 1; i < lim; i++){
        int tmp = i;
        while(que[l].f < i-(i%que[l].s)){
            l++;
        }
        dp[i] = dp[que[l].f]+1;
        while(pp[tmp]){
            int prv = pp[tmp];
            while(pp[tmp] == prv){
                tmp/=prv;
            }
            if(mm[prv])que[r++] = {i, prv};
        }
    }
    while(q--){
        int x;
        cin >> x;
        if(x >= lim)cout << "oo";
        else cout << dp[x];
        cout << "\n";
    }


}

• Subtask 1: 15.555555555555555 / 20
• Subtask 2: 11.11111111111111 / 20
• Subtask 3: 24.285714285714285 / 60