GCJ 2016 Qualification Round C: Coin 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; } }