This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
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);
}
for(int i = 0; i < k - 1; i++) p(m[i]);
ans = n;
find(m[k - 1]);
cout << n / ans;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |