oj.uz

답안 #97327

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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