Submission #614567

#TimeUsernameProblemLanguageResultExecution timeMemory
6145671binStrongbox (POI11_sej)C++14
100 / 100
193 ms2732 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> d; 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); 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){ d.emplace_back(i); d.emplace_back(x / i); } sort(all(d)); for(ll x : d) if(chk(x)) { cout << n / x; break; } 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...