結果

問題 No.2 素因数ゲーム
ユーザー satori16satori16
提出日時 2016-08-09 04:39:18
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 2,725 bytes
コンパイル時間 851 ms
コンパイル使用メモリ 82,832 KB
実行使用メモリ 15,468 KB
最終ジャッジ日時 2024-11-07 07:37:09
合計ジャッジ時間 25,417 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <cstdint>

//自信ないなー。
//なんかうごいてる？？

typedef std::vector<bool> PBox;
typedef std::map<std::uint64_t, std::uint64_t> PFType;

PBox MakePrime(const std::uint64_t& N) {
	PBox P(N+1,true);
	P[0] = false;
	P[1] = false;
	for (std::uint64_t i = 2; i <= N; i++) {
		if (!P[i])continue;
		for (std::uint64_t j = 2; i*j <= N; j++) {
			P[i*j] = false;
		}
	}

	return P;
}

PFType MakePrimeFactor(const std::uint64_t& N,const PBox& PB) {
	std::uint64_t C = 0;
	std::uint64_t V = N;
	PFType PF;
	for (std::uint64_t i = 0; i <= V; i++) {
		if (!PB[i]) continue;
		C = 0;
		while (V%i == 0) {
			V /= i;
			C++;
		}
		if(C!= 0) PF[i] = C;
	}
	return PF;
}

bool ErazeZero(PFType& P) {
	for (PFType::iterator i = P.begin(); i != P.end(); i++) {
		if (i->second == 0) {
			PFType::iterator T = i;
			i--;
			P.erase(T);
			if (i == P.end()) break;
		}
	}
	return true;
}

PFType MakeStuts(PFType& P) {
	PFType R;
	std::uint64_t L = 2;
	for (auto&o : P) {
		R[o.first] = o.second;
		if (R[o.first] > L)R[o.first] = L;
	}
	return R;
}

std::uint64_t MustNeedHand(PFType& P) {
	std::uint64_t R = 0;

	for (auto&o : P) {
		R += o.second;
	}
	return R;
}


bool Think(PFType& P) {
	PFType S = MakeStuts(P);
	std::uint64_t NH = MustNeedHand(S);
	std::uint64_t AH = MustNeedHand(P);

		for (auto&o : P) {
			if (NH % 2) {//必要ハンド数が奇数の時は・・・。
				if (AH % 2) {//必要ハンド数が奇数のときは・・・。
					if (o.second > 0) {//カテゴリ消滅
						o.second = 0;
						return true;
					}
				}else {
					if (o.second > 1) {//カテゴリーのラス一残してパス。
						o.second = 1;
						return true;
					}
				}
			}
			else {//偶数の時
				if (o.second > 2) {
					o.second = 1;
				}
			}
		}
		for (auto&o : P) {//ここに来るときは各要素1だと思うので、カテゴリ消去を強制する。
			o.second = 0;
			return true;
		}

		return false;
}

bool MakeHoge(const std::uint64_t& N) {
	std::uint64_t C = 0;
	PBox PB= MakePrime(N);
	PFType PF = MakePrimeFactor(N, PB);
	std::uint64_t V = N;

	while (PF.size() != 0) {
		if (Think(PF) == false) throw 0xDEADBEEF;
		ErazeZero(PF);
		C++;
	}

	return (C%2) != 0;
}

bool Show(bool F) {
	std::cout << (F ? "Alice" : "Bob") << std::endl;
	return true;
}

int main() {
	bool R = false;
	std::uint64_t N;
#if 0
	N = 4;
	R = MakeHoge(N);
	std::cout << N << ':';
	Show(R);
	N = 11;
	R = MakeHoge(N);
	std::cout << N << ':';
	Show(R);
	N = 24;
	R = MakeHoge(N);
	std::cout << N << ':';
	Show(R);
	N = 600;
	R = MakeHoge(N);
	std::cout << N << ':';
	Show(R);
#else
	std::cin >> N;
	R = MakeHoge(N);
	Show(R);
#endif
	return true;
}
0