GCJ 2016 Qualification Round C: Coin Jam

問題

Dashboard - Qualification Round 2016 - Google Code Jam

解法

愚直にやる。N=16の答えを2つ並べるとN=32の答えになる。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll generate(ll mask, ll b) {
  ll ans = 0;
  ll a = 1;
  while (mask > 0) {
    if (mask & 1) ans += a;
    mask >>= 1;
    a *= b;
  }
  return ans;
}

ll get_divisor(ll checker, const vector<int> &primes) {
  ll N = min((ll)primes.size(), (ll)sqrt(checker) + 2);
  for (const auto p : primes) {
    if (checker % p == 0) return p;
    if (p > N) break;
  }
  return -1;
}

vector<int> eratosthenes(int N) {
  vector<bool> is_prime(N + 1, true);
  vector<int> primes;
  is_prime[0] = false;
  is_prime[1] = false;
  for (int i = 2; i <= N; ++i)
    if (is_prime[i]) {
      primes.push_back(i);
      for (int j = i * 2; j <= N; j += i) {
        is_prime[j] = false;
      }
    }
  return primes;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N = 16;
  int J = 500;
  vector<int> primes = eratosthenes(1e8);
  vector<vector<ll>> ans;
  vector<ll> subans(10);
  for (ll i = 0; i < (1 << (N - 2)); ++i) {
    if ((i + 1) % 100000 == 0) cerr << (i + 1) << endl;
    ll mask = (i << 1) + 1 + (1 << (N - 1));
    subans[0] = mask;
    for (int b = 2; b <= 10; ++b) {
      ll checker = generate(mask, b);
      ll d = get_divisor(checker, primes);
      if (d < 0) goto next;
      subans[b - 1] = d;
    }
    ans.push_back(subans);
    if (ans.size() == J) break;
  next:;
  }

  cout << "Case #1:" << endl;
  for (const auto &v : ans) {
    cout << static_cast<bitset<16>>(v[0]);
    cout << static_cast<bitset<16>>(v[0]);
    for (int i = 1; i < v.size(); ++i) {
      cout << " " << v[i];
    }
    cout << endl;
  }
}