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];
vector<ll> d, 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){
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 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... |