結果
問題 | No.2 素因数ゲーム |
ユーザー | Onju |
提出日時 | 2015-02-11 16:23:51 |
言語 | C++11 (gcc 11.4.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,542 bytes |
コンパイル時間 | 401 ms |
コンパイル使用メモリ | 62,360 KB |
最終ジャッジ日時 | 2024-04-27 02:06:33 |
合計ジャッジ時間 | 872 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In function ‘std::vector<int>* getPrime(int)’: main.cpp:17:23: error: ‘sqrt’ was not declared in this scope 17 | int sn = (int)sqrt(N); | ^~~~
ソースコード
#include <iostream> #include <climits> #include <functional> #include <algorithm> #include <vector> #include <cstring> #include <cstdlib> #define N_MAX 100000000 #define P_SIZE 30 //高々26・・のはず using namespace std; vector<int>* getPrime(int N) { auto list = new bool[N + 1]; auto prime = new vector<int>(); int sn = (int)sqrt(N); list[0] = list[1] = false; for (int i = 2; i <= N; ++i) list[i] = true; for (int i = 2; i <= sn; ++i) { if (list[i]) { int jmax = N / i; for (int j = i; j <= jmax; ++j) list[i*j] = false; } } for (int i = 2; i <= N; ++i) { if (list[i]) prime->push_back(i); } delete[] list; return prime; } bool DP(char x[], int n) { switch (n) { case 0: return false; case 1: return true; } bool ans = false; for (int i = 0; !ans && i < n; ++i) { for (int j = 1; !ans && j <= x[i]; ++j) { x[i] -= j; if (!x[i]) { swap(x[i], x[n-1]); ans = !DP(x, n - 1); swap(x[i], x[n-1]); } else ans = !DP(x, n); x[i] += j; } } return ans; } int main() { char name[][6] = { "Alice", "Bob" }; int N, Pnum=0, Psize=0; char P[P_SIZE]; memset(P, 0, sizeof(char)*P_SIZE); cin >> N; auto prime = getPrime(N); int temp = 0, pn = -1; for (auto it = prime->begin(); it != prime->end(); ++it) { while (!(N%(*it))) { if (*it != temp) { temp = *it; ++pn; } N /= (*it); ++P[pn]; } } sort(P, P + P_SIZE, greater<char>()); cout << name[DP(P, strlen(P)) ? 0 : 1] << endl; delete prime; return 0; }