Submission #97327

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
97327	2019-02-15T07:22:44 Z	tmwilliamlin168	Strongbox (POI11_sej)	C++14	100 / 100	697 ms	4984 KB

#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll n, m, ans=1e18, p[12], n2;
int k, ps;
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;
}

Subtask #1
7.0 / 7.0

#	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	1 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct

Subtask #3
7.0 / 7.0

#	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	3 ms	384 KB	Output is correct

Subtask #4
7.0 / 7.0

#	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	4 ms	384 KB	Output is correct

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	15 ms	384 KB	Output is correct
4	Correct	10 ms	640 KB	Output is correct

Subtask #6
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	25 ms	1016 KB	Output is correct
3	Correct	131 ms	384 KB	Output is correct
4	Correct	27 ms	1016 KB	Output is correct

Subtask #7
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	126 ms	400 KB	Output is correct
4	Correct	23 ms	1016 KB	Output is correct

Subtask #8
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	424 KB	Output is correct
2	Correct	25 ms	1144 KB	Output is correct
3	Correct	87 ms	400 KB	Output is correct
4	Correct	23 ms	1152 KB	Output is correct

Subtask #9
7.0 / 7.0

#	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	15 ms	384 KB	Output is correct
4	Correct	28 ms	1116 KB	Output is correct

Subtask #10
7.0 / 7.0

#	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	90 ms	512 KB	Output is correct
4	Correct	25 ms	1152 KB	Output is correct

Subtask #11
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	1404 KB	Output is correct
2	Correct	138 ms	1528 KB	Output is correct
3	Correct	102 ms	2168 KB	Output is correct
4	Correct	150 ms	2808 KB	Output is correct
5	Correct	95 ms	2168 KB	Output is correct

Subtask #12
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	128 ms	3040 KB	Output is correct
2	Correct	490 ms	4216 KB	Output is correct
3	Correct	146 ms	3192 KB	Output is correct
4	Correct	146 ms	2936 KB	Output is correct
5	Correct	148 ms	3200 KB	Output is correct

Subtask #13
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	165 ms	3216 KB	Output is correct
2	Correct	621 ms	4984 KB	Output is correct
3	Correct	186 ms	3848 KB	Output is correct
4	Correct	230 ms	3960 KB	Output is correct
5	Correct	173 ms	3708 KB	Output is correct

Subtask #14
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	164 ms	2936 KB	Output is correct
2	Correct	697 ms	4904 KB	Output is correct
3	Correct	206 ms	3804 KB	Output is correct
4	Correct	215 ms	3852 KB	Output is correct
5	Correct	216 ms	3832 KB	Output is correct

Submission #97327

Compilation message