Submission #97328

# Submission time Handle Problem Language Result Execution time Memory
97328 2019-02-15T07:24:04 Z tmwilliamlin168 Strongbox (POI11_sej) C++14
100 / 100
261 ms 1164 KB
#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll n, m, ans=1e18, p[12], n2;
int k, ps;
unordered_set<ll> v;

void dfs(ll u, bool ua=0) {
	if(ua)
		ans=min(u, ans);
	v.insert(u);
	for(int i=0; i<ps; ++i)
		if(u%p[i]==0&&v.find(u/p[i])==v.end())
			dfs(u/p[i], ua);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;
	n2=n;
	for(ll i=2; i*i<n; ++i) {
		if(n%i)
			continue;
		p[ps++]=i;
		while(n%i==0)
			n/=i;
	}
	if(n>0)
		p[ps++]=n;
	for(int i=0; i<k; ++i)
		cin >> m, dfs(__gcd(m, n2), i==k-1);
	cout << n2/ans;
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 428 KB Output is correct
3 Correct 13 ms 256 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 11 ms 1032 KB Output is correct
3 Correct 122 ms 384 KB Output is correct
4 Correct 14 ms 1016 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 115 ms 384 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 31 ms 504 KB Output is correct
2 Correct 13 ms 1024 KB Output is correct
3 Correct 91 ms 384 KB Output is correct
4 Correct 11 ms 1024 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 10 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 20 ms 384 KB Output is correct
4 Correct 14 ms 1024 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 84 ms 376 KB Output is correct
4 Correct 13 ms 1152 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 72 ms 416 KB Output is correct
2 Correct 65 ms 504 KB Output is correct
3 Correct 86 ms 1052 KB Output is correct
4 Correct 135 ms 1144 KB Output is correct
5 Correct 70 ms 1164 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 127 ms 412 KB Output is correct
2 Correct 223 ms 1024 KB Output is correct
3 Correct 128 ms 748 KB Output is correct
4 Correct 114 ms 1016 KB Output is correct
5 Correct 158 ms 1116 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 147 ms 384 KB Output is correct
2 Correct 242 ms 1024 KB Output is correct
3 Correct 158 ms 1116 KB Output is correct
4 Correct 188 ms 1144 KB Output is correct
5 Correct 162 ms 1016 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 146 ms 384 KB Output is correct
2 Correct 261 ms 1152 KB Output is correct
3 Correct 183 ms 1144 KB Output is correct
4 Correct 185 ms 1144 KB Output is correct
5 Correct 161 ms 1060 KB Output is correct