Submission #332610

#TimeUsernameProblemLanguageResultExecution timeMemory
332610thecodingwizardStrongbox (POI11_sej)C++11
28 / 100
372 ms4844 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define ii pair<int, int> #define f first #define s second #define pb push_back #define mp make_pair #define all(x) x.begin(), x.end() #define F0R(i, n) for (int i = 0; i < n; i++) #define FOR(i, a, b) for (int i = a; i < b; i++) #define inf 1000000010 vector<int> primes; ll ans = 1e18; set<ll> illegalNumbers; void handleNumber(ll n, bool updAns) { illegalNumbers.insert(n); if (updAns) ans = min(ans, n); for (int p : primes) { if (n % p == 0 && illegalNumbers.count(n/p) == 0) { handleNumber(n/p, updAns); } } } int main() { cin.tie(0)->sync_with_stdio(0); ll n; int k; cin >> n >> k; ll origN = n; if (k == 1) { cout << n << endl; return 0; } for (ll i = 2; i*i <= n; i++) { if (n%i == 0) { primes.pb(i); while (n%i == 0) n /= i; } } F0R(i, k) { ll x; cin >> x; handleNumber(__gcd(origN, x), i==k-1); } cout << origN/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...