Submission #614596

#TimeUsernameProblemLanguageResultExecution timeMemory
6145961binStrongbox (POI11_sej)C++14
21 / 100
99 ms4444 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], ans; vector<ll> v; ll gcd(ll a, ll b){ if(!b) return a; return gcd(b, a % b); } int chk(ll& x){ for(ll& y : v) if(y % 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++) v.emplace_back(m[i]); sort(all(v)); v.erase(unique(all(v)), v.end()); x = m[k - 1]; for(ll i = 1; i * i <= x; i++) if(x % i == 0){ if(chk(i)) { ans = n / i; break; } else ans = n / (x / i); } cout << 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...