Submission #332599

#TimeUsernameProblemLanguageResultExecution timeMemory
332599thecodingwizardStrongbox (POI11_sej)C++11
0 / 100
1047 ms19820 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define ii pair<int, int> #define f first #define s second #define pb push_back #define mp make_pair #define all(x) x.begin(), x.end() #define F0R(i, n) for (int i = 0; i < n; i++) #define FOR(i, a, b) for (int i = a; i < b; i++) #define inf 1000000010 bool no[10000001]; bool notPrime[10000001]; int main() { cin.tie(0)->sync_with_stdio(0); ll n; int k; cin >> n >> k; if (k == 1) { cout << n << endl; return 0; } ll bad[k-1]; F0R(i, k-1) cin >> bad[i]; ll good; cin >> good; ll gcd = __gcd(n, good); assert(gcd <= 1e7); for (int i = 2; i <= gcd; i++) { if (!notPrime[i]) { for (int j = i+i; j <= gcd; j += i) { notPrime[j] = true; } } } for (int i = 2; i <= gcd; i++) { if (notPrime[i]) continue; bool isBad = false; F0R(j, k-1) if (bad[j] % i == 0) isBad = true; if (isBad) { for (int j = i; j <= gcd; j += i) { no[j] = true; } } } for (int i = 2; i <= gcd; i++) { if (gcd % i == 0 && !no[i]) { cout << n/i << endl; return 0; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...