Project Euler - Problem 200
Find the 200th prime-proof sqube containing the contiguous sub-string "200"
p2q3 (p, q は異なる素数)で表せる数をスキューブ(sqube)と定義する. 例えば, 200 = 5223, 120072949 = 232613 である.
最初の5つのスキューブは 72, 108, 200, 392, 500 である.
面白いことに, 200はどの1桁の数字を変更しても素数とならない最小の数である. この特徴をもつ数字を"耐素数性のある"(prime-proof)数と呼ぶ. 連続する部分文字列に "200" を持つ次の耐素数性のあるスキューブは 1992008 である.
連続する部分文字列に "200" を持つ 200 番目の耐素数性のあるスキューブを求めよ.
[訳注: sqube(スキューブ): square(平方数)とcube(立方数)からの造語]
(日本語訳より)
最初の5つのスキューブは 72, 108, 200, 392, 500 である.
面白いことに, 200はどの1桁の数字を変更しても素数とならない最小の数である. この特徴をもつ数字を"耐素数性のある"(prime-proof)数と呼ぶ. 連続する部分文字列に "200" を持つ次の耐素数性のあるスキューブは 1992008 である.
連続する部分文字列に "200" を持つ 200 番目の耐素数性のあるスキューブを求めよ.
[訳注: sqube(スキューブ): square(平方数)とcube(立方数)からの造語]
(日本語訳より)
200 問目だからかやたらと 200 を出してきて草
やってみたらやるだけだった
ある程度の大きさまでの素数を生成して,ある程度の大きさ以下のスキューブを列挙して,"200" が含まれているかどうか調べて,耐素数性のあるものをピックアップして,200 番目の要素を答えて,終わり
ABC の D 問題くらい?
#include "bits/stdc++.h" using namespace std; typedef long long ll; #define REP(i,n) FOR(i,0,n) #define all(x) (x).begin(), (x).end() #define MAX 1000000 #define MMAX 1000000000000LL vector<int> ps; bool p[MAX + 1]; vector<ll> squbes; inline ll sqube(ll p, ll q) { return p * p * q * q * q; } bool is_prime(ll n) { ll i; if (n < 2) return false; if (n == 2) return true; if (n % 2 == 0) return false; for (i = 3; i * i <= n; i += 2) { if (n % i == 0) return false; } return true; } bool primeproof(ll n) { ll x = n, y, d = 1; while (x) { ll r = x % 10 * d; x /= 10; y = n - r; for (ll z = y, c = 0; c < 10; z += d, c++) { if (z <= MAX) { if (p[z]) return false; } else { if (is_prime(z)) return false; } } d *= 10; } return true; } bool contain200(ll n) { while (n) { if (n % 1000 == 200) return true; n /= 10; while (n % 100) n /= 10; } return false; } int main() { clock_t start, end; start = clock(); //cin.tie(0); //ios::sync_with_stdio(false); Fill(p, true); p[0] = p[1] = false; for (int i = 2; i * i <= MAX; i++) if (p[i]) for (int j = i * i; j <= MAX; j += i) p[j] = false; REP(i, MAX) if (p[i]) ps.push_back(i); for (int i = 0; i < ps.size(); i++) { for (int j = 0; j < ps.size(); j++) { if (i == j) continue; ll sqb = sqube(ps[i], ps[j]); if (sqb > MMAX) break; squbes.push_back(sqb); } } sort(all(squbes)); int count = 0; REP(i, SZ(squbes)) if (contain200(squbes[i]) && primeproof(squbes[i])) { count++; if (count == 200) { cout << squbes[i] << endl; break; } } end = clock(); printf("%d msec.\n", end - start); return 0; }