Submission #1247785

#TimeUsernameProblemLanguageResultExecution timeMemory
1247785piedavBrunhilda’s Birthday (BOI13_brunhilda)C++20
25.24 / 100
569 ms311324 KiB
#include <iostream> #include <vector> #include <set> using namespace std; #define int long long int32_t main() { ios::sync_with_stdio(false); cin.tie(NULL); int m, q; cin >> m >> q; vector<int> p (m); vector<bool> mults (10000001, 0); //quickly check if the product > 10^7 int product = 1; vector<int> largestPrime (10000001, 1); for(int i = 0; i < m; ++i) { cin >> p[i]; if(product <= 10000000) product *= p[i]; for(int j = p[i]; j <= 10000001; j += p[i]) { mults[j] = 1; largestPrime[j] = p[i]; } } vector<int> multiples; for(int i = 0; i <= 10000001; ++i) { if(mults[i]) multiples.push_back(i); } vector<int> best (min(product+1, 10000001LL), 10000001); for(int i = 0; i < m; ++i) { best[best.size()-1] = min(best[best.size()-1], (long long)((best.size()-1)/p[i]*p[i])); } for(int i = best.size()-2; i >= 0; --i) { best[i] = min(best[i+1], (i+1)-largestPrime[i+1]); } int maxn = min(product, 10000001LL); vector<int> ans (maxn+1, 1e18); //max distance for(int i = 0; i < p[m-1]; ++i) { ans[i] = 1; } for(int i = p[m-1]; i < maxn+1; ++i) { ans[i] = ans[best[i]] + 1; } int n; for(int i = 0; i < q; ++i) { cin >> n; if(n >= product) { cout << "oo\n"; continue; } cout << ans[n] << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...