제출 #97328

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97328		tmwilliamlin168	Strongbox (POI11_sej)	C++14	100 / 100	261 ms	1164 KiB

sej

#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;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 8 / 8
• Subtask 14: 8 / 8