Submission #614623

#TimeUsernameProblemLanguageResultExecution timeMemory
6146231binStrongbox (POI11_sej)C++14
100 / 100
827 ms2688 KiB
#include <bits/stdc++.h> using namespace std; #define all(v) v.begin(), v.end() typedef long long ll; const int NMAX = 3e5 + 5; ll n, x, k, m[NMAX], sz; vector<ll> da, db; ll gcd(ll a, ll b){ if(!b) return a; return gcd(b, a % b); } int chk(ll& x){ for(int i = 0; i < sz; i++) if(m[i] % x == 0) return 0; return 1; } int main(void){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; for(int i = 0; i < k; i++) cin >> m[i], m[i] = gcd(m[i], n); sort(m, m + k - 1); for(int i = 0; i < k - 1; i++) if(m[i] != m[i + 1]) m[sz++] = m[i]; x = m[k - 1]; for(ll i = 1; i * i <= x; i++) if(x % i == 0){ da.emplace_back(i); db.emplace_back(x / i); } for(ll& x : da) if(chk(x)) { cout << n / x; return 0; } for(int i = db.size() - 1; i >= 0; i--) if(chk(db[i])) { cout << n / db[i]; 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...