Submission #615536

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
615536	2022-07-31T10:21:58 Z	1bin	Strongbox (POI11_sej)	C++14	35 / 100	1000 ms	6716 KB

#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], sz, ans;
vector<ll> d;
 
ll gcd(ll a, ll b){
    if(!b) return a;
    return gcd(b,  a % b);
}
 
set<ll> s;
 
void p(ll x){
    s.emplace(x);
    for(ll& y : d)
        if(x % y == 0 && s.find(x / y) == s.end()) p(x / y);
    return;
}

void find(ll x){
    ans = min(ans, x);
    for(ll& y : d)
        if(x % y == 0 && s.find(x / y) == s.end()) find(x / y);
    return;
}

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);
    x = n;
    for(ll i = 2; i * i <= n; i++) 
        if(x % i == 0){
            while(x % i == 0) x /= i;
            d.emplace_back(i);
        }
        
    for(int i = 0; i < k - 1; i++) p(m[i]);
    ans = n;
    find(m[k - 1]);
    cout << n / ans;
    return 0;
}

Subtask #1
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	328 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	340 KB	Output is correct
2	Correct	6 ms	332 KB	Output is correct
3	Correct	8 ms	212 KB	Output is correct
4	Execution timed out	1088 ms	468 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #6
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	344 KB	Output is correct
2	Correct	48 ms	1040 KB	Output is correct
3	Correct	86 ms	212 KB	Output is correct
4	Execution timed out	1090 ms	728 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #7
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	340 KB	Output is correct
2	Correct	258 ms	340 KB	Output is correct
3	Correct	88 ms	340 KB	Output is correct
4	Correct	799 ms	856 KB	Output is correct

Subtask #8
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	340 KB	Output is correct
2	Correct	58 ms	984 KB	Output is correct
3	Correct	86 ms	340 KB	Output is correct
4	Execution timed out	1086 ms	844 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #9
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	340 KB	Output is correct
2	Correct	54 ms	340 KB	Output is correct
3	Correct	56 ms	340 KB	Output is correct
4	Execution timed out	1096 ms	728 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #10
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	340 KB	Output is correct
2	Correct	50 ms	340 KB	Output is correct
3	Correct	89 ms	340 KB	Output is correct
4	Execution timed out	1095 ms	716 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #11
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	88 ms	2112 KB	Output is correct
2	Correct	82 ms	2252 KB	Output is correct
3	Correct	466 ms	2816 KB	Output is correct
4	Correct	116 ms	3788 KB	Output is correct
5	Execution timed out	1084 ms	2512 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #12
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	102 ms	4504 KB	Output is correct
2	Correct	310 ms	5536 KB	Output is correct
3	Execution timed out	1084 ms	4188 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #13
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	97 ms	5156 KB	Output is correct
2	Correct	383 ms	6684 KB	Output is correct
3	Execution timed out	1067 ms	5284 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #14
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	108 ms	4828 KB	Output is correct
2	Correct	364 ms	6716 KB	Output is correct
3	Correct	144 ms	5532 KB	Output is correct
4	Correct	163 ms	5696 KB	Output is correct
5	Execution timed out	1092 ms	5196 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Submission #615536

Compilation message