Submission #615540

#TimeUsernameProblemLanguageResultExecution timeMemory
6155401binStrongbox (POI11_sej)C++14
100 / 100
346 ms5704 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, ans; vector<ll> d; ll gcd(ll a, ll b){ if(!b) return a; return gcd(b, a % b); } set<ll> s; void p(ll x){ s.emplace(x); for(ll& y : d) if(x % y == 0 && s.find(x / y) == s.end()) p(x / y); return; } void find(ll x){ ans = min(ans, x); s.emplace(x); for(ll& y : d) if(x % y == 0 && s.find(x / y) == s.end()) find(x / y); return; } 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); x = n; for(ll i = 2; i * i <= n; i++) if(x % i == 0){ while(x % i == 0) x /= i; d.emplace_back(i); } if(x > 1) d.emplace_back(x); for(int i = 0; i < k - 1; i++) p(m[i]); ans = n; find(m[k - 1]); cout << n / ans; 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...