ACM/ICPC国内予選1問目
4時前に起きて準決勝一回戦を見て、ごみ捨てに行ってから一通りやってみました。ABDが終わってEのパースしてる間に時間切れ。準備してないとやっぱつらいなぁ。更新ネタをストックするため一問ずつさらしてみます。以下コード。
#include <stdio.h> #include <iostream> using namespace std; static unsigned char prim_table[1000000]; int main() { // make primary number table memset(prim_table, 1, 1000000); prim_table[0] = 0; prim_table[1] = 0; for (int i = 2; i < 1000000; i++) { if (prim_table[i] == 0) continue; // printf("%d is prime number.\n", i); for (int j = 2 * i; j < 1000000; j += i) { prim_table[j] = 0; } } int a, d, n; while (true) { scanf("%d %d %d", &a, &d, &n); if (a == 0 && d == 0 && n == 0) break; for (int i = a; i < 1000000; i += d) { if (prim_table[i] == 0) continue; n--; if (n <= 0) { printf("%d\n", i); break; } } } }
素数の求め方って何だっけ……ってとこから始まったので微妙に時間かかってます。15分。まぁありがちな問題ですね。素数テーブルが100万なのはカン。そんなに計算重いわけじゃないのでタイムアップにはならないと思います。