oj.uz

답안 #200612

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
200612 2020-02-07T15:27:20 Z Sorting Strongbox (POI11_sej) C++14
100 / 100
 440 ms 6776 KB 
#include <bits/stdc++.h>

using namespace std;

vector<long long > m, primes;
long long ans;

set<long long> visited;

void dfs(long long num, bool check){
	visited.insert(num);
	if(check)
		ans = min(ans, num);

	for(long long prime: primes)
		if(num % prime == 0 && !visited.count(num / prime))
			dfs(num / prime, check);
}

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

	long long n, k;
	cin >> n >> k;
	ans = n;

	m.resize(k);
	for(int i = 0; i < k; ++i)
		cin >> m[i];
	
	long long n_copy = n;
	for(long long d = 2; d * d <= n_copy; ++d){
		if(n_copy % d == 0){
			primes.push_back(d);
			while(n_copy % d == 0)
				n_copy /= d;
		}
	}
	if(n_copy > 1)
		primes.push_back(n_copy);

	for(int i = 0; i < k; ++i){
		dfs(__gcd(n, m[i]), i == k - 1);
	}

	cout << n / ans << "\n";
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 248 KB Output is correct
4 Correct 5 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct

Subtask #4
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 380 KB Output is correct
3 Correct 7 ms 376 KB Output is correct

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 15 ms 376 KB Output is correct
4 Correct 11 ms 632 KB Output is correct

Subtask #6
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 23 ms 1016 KB Output is correct
3 Correct 105 ms 376 KB Output is correct
4 Correct 22 ms 1016 KB Output is correct

Subtask #7
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 109 ms 376 KB Output is correct
4 Correct 20 ms 1016 KB Output is correct

Subtask #8
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 376 KB Output is correct
2 Correct 22 ms 1144 KB Output is correct
3 Correct 77 ms 380 KB Output is correct
4 Correct 21 ms 1144 KB Output is correct

Subtask #9
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 16 ms 380 KB Output is correct
4 Correct 22 ms 1144 KB Output is correct

Subtask #10
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 75 ms 404 KB Output is correct
4 Correct 23 ms 1144 KB Output is correct

Subtask #11
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 2172 KB Output is correct
2 Correct 52 ms 2296 KB Output is correct
3 Correct 70 ms 2940 KB Output is correct
4 Correct 96 ms 3960 KB Output is correct
5 Correct 61 ms 3064 KB Output is correct

Subtask #12
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 4600 KB Output is correct
2 Correct 339 ms 5624 KB Output is correct
3 Correct 86 ms 4604 KB Output is correct
4 Correct 92 ms 3960 KB Output is correct
5 Correct 98 ms 4764 KB Output is correct

Subtask #13
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 5216 KB Output is correct
2 Correct 440 ms 6648 KB Output is correct
3 Correct 115 ms 5500 KB Output is correct
4 Correct 125 ms 5912 KB Output is correct
5 Correct 115 ms 5800 KB Output is correct

Subtask #14
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 4856 KB Output is correct
2 Correct 404 ms 6776 KB Output is correct
3 Correct 122 ms 5624 KB Output is correct
4 Correct 124 ms 5880 KB Output is correct
5 Correct 121 ms 5752 KB Output is correct