Submission #167923

#TimeUsernameProblemLanguageResultExecution timeMemory
167923ThuleanxStrongbox (POI11_sej)C++14
100 / 100
236 ms6148 KiB
#include <bits/stdc++.h> using namespace std; unordered_set<long long> vis; vector<int> primes; long long ans; void brute_force(long long v, bool save) { if (save) ans = min(ans, v); vis.insert(v); for (long long p : primes) if (v%p==0 && !vis.count(v / p)) brute_force(v/p, save); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; long long m; cin>>m>>n; long long a[n]; for (int i = 0; i < n; i++) { cin>>a[i]; a[i] = __gcd(a[i], m); } for (long long p = 2, x = a[n-1]; p*p <= x; p++) { if (x%p == 0) { primes.push_back(p); while (x%p == 0) x /= p; } if ((p+1)*(p+1)>x && x>1) primes.push_back(x); } ans = m; for (int i = 0; i < n; i++) brute_force(__gcd(a[i], a[n-1]), i == n-1); cout << m/ans << endl; 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...