Submission #644474

#TimeUsernameProblemLanguageResultExecution timeMemory
644474GusterGoose27Strongbox (POI11_sej)C++11
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const ll MAXN = 1e14; const int MAXK = 25e4; const int MAXF = 1e6; ll n; int k; ll elems[MAXK]; ll gcd(ll a, ll b) { if (a > b) return gcd(b, a); if (a == 0) return b; return gcd(b%a, a); } vector<ll> primes; vector<ll> nprimes; bool is_prime[(int) sqrt(MAXN)+1]; vector<pii> factorizations[MAXK]; int state[MAXF]; // 0 unvisited, 2 descended from k, 1 blocked ll val[MAXF]; int hshs[MAXK]; int coeffs[MAXK]; int mxh = 0; ll ans = 2; void make_primes(ll mx) { fill(is_prime, is_prime+mx+1, 1); for (int i = 2; i <= mx; i++) { if (!is_prime[i]) continue; primes.push_back(i); for (int j = 2*i; j <= mx; j+= i) is_prime[j] = 0; } } void factorize(ll target, vector<pii> &factored) { // prime for (int i = 0; i < primes.size() && target > 1; i++) { int c = 0; while (target % primes[i] == 0) { target /= primes[i]; c++; nprimes.push_back(primes[i]); } if (c) factored.push_back(pii(primes[i], c)); } if (target != 1) { nprimes.push_back(target); factored.push_back(pii(target, 1)); } } void factorize2(ll target, vector<pii> &factored) { // prime for (int i = 0; i < nprimes.size(); i++) { int c = 0; while (target % nprimes[i] == 0) { target /= nprimes[i]; c++; } factored.push_back(pii(nprimes[i], c)); } } void make_coeffs() { int mult = 1; for (int i = 0; i < nprimes.size(); i++) { coeffs[i] = mult; mult *= (factorizations[k-1][i].second+1); } } int hsh(vector<pii> &factored) { int r = 0; for (int i = 0; i < nprimes.size(); i++) { r += factored[i].second*coeffs[i]; } mxh = max(mxh, r); return r; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> k; for (int i = 0; i < k; i++) { cin >> elems[i]; if (elems[i] == 0) elems[i] = n; ans -= (elems[i] == n); } if (elems[i] == n && k < n) ans = 2; elems[k-1] = gcd(elems[k-1], n); for (int i = 0; i < k-1; i++) elems[i] = gcd(elems[i], elems[k-1]); make_primes((int) sqrt(n)); factorize(elems[k-1], factorizations[k-1]); make_coeffs(); hshs[k-1] = hsh(factorizations[k-1]); state[hshs[k-1]] = 2; val[hshs[k-1]] = elems[k-1]; for (int i = 0; i < k-1; i++) { factorize2(elems[i], factorizations[i]); hshs[i] = hsh(factorizations[i]); state[hshs[i]] = 1; val[hshs[i]] = elems[i]; } for (int i = mxh; i >= 0; i--) { if (state[i] == 0) continue; if (state[i] == 2) ans = max(ans, n/val[i]); for (int p = 0; p < nprimes.size(); p++) { int v = i/coeffs[p]; if (v % (factorizations[k-1][p].second+1) == 0) continue; int nxt = i-coeffs[p]; if (state[nxt] == 1 || (state[nxt] == 2 && state[i] == 2)) continue; val[nxt] = val[i]/nprimes[p]; state[nxt] = state[i]; } } cout << ans << "\n"; }

Compilation message (stderr)

sej.cpp: In function 'void factorize(ll, std::vector<std::pair<int, int> >&)':
sej.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for (int i = 0; i < primes.size() && target > 1; i++) {
      |                  ~~^~~~~~~~~~~~~~~
sej.cpp: In function 'void factorize2(ll, std::vector<std::pair<int, int> >&)':
sej.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i = 0; i < nprimes.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~
sej.cpp: In function 'void make_coeffs()':
sej.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for (int i = 0; i < nprimes.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~
sej.cpp: In function 'int hsh(std::vector<std::pair<int, int> >&)':
sej.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for (int i = 0; i < nprimes.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~
sej.cpp: In function 'int main()':
sej.cpp:94:12: error: 'i' was not declared in this scope
   94 |  if (elems[i] == n && k < n) ans = 2;
      |            ^
sej.cpp:112:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |   for (int p = 0; p < nprimes.size(); p++) {
      |                   ~~^~~~~~~~~~~~~~~~