using System; using System.IO; using System.Linq; using System.Collections.Generic; using System.Text; public class Program { public void Proc() { int num = int.Parse(Reader.ReadLine()); CreatePrimeList(num); string ans = "Bob"; if(IsWin(PrimeDevide(num).Select(a=>a.Value).OrderBy(a=>a).ToList())) { ans = "Alice"; } Console.WriteLine(ans); } private Dictionary PrimeDevide(int num) { int tmp = num; Dictionary ret = new Dictionary(); int idx = 0; while(tmp>1) { if(tmp%PrimeList[idx]==0) { if(!ret.ContainsKey(PrimeList[idx])) { ret.Add(PrimeList[idx], 1); } else { ret[PrimeList[idx]]++; } tmp = tmp / PrimeList[idx]; } else { idx++; } } return ret; } private void CreatePrimeList(int num) { bool[] flags = new bool[num + 1]; List list = new List(); for (int i = 2; i < flags.Length; i++) { if (flags[i]) { continue; } list.Add(i); int max = num / i; for (int j = 1; j <= max; j++) { flags[i * j] = true; } } this.PrimeList = list.ToArray(); } private Dictionary dic = new Dictionary(); private bool IsWin(List list) { string key = string.Join("#", list); if(dic.ContainsKey(key)) { return dic[key]; } if(list.Count == 0) { dic[key] = false; return false; } if(list.Count == 1) { dic[key] = true; return true; } bool canWin = false; int idx = -1; if (list.Any(a => a > 2)) { idx = list.FindIndex(a => a > 2); List subList = new List(list); subList[idx] = 2; bool ret = IsWin(subList.OrderBy(a => a).ToList()); if(!ret) { canWin = true; } if (!canWin) { subList = new List(list); subList[idx] = 1; ret = IsWin(subList.OrderBy(a => a).ToList()); if (!ret) { canWin = true; } } if(!canWin) { subList = new List(list); subList.RemoveAt(idx); ret = IsWin(subList); if (!ret) { canWin = true; } } } if((!canWin) && list.Any(a=>a==2)) { idx = list.FindIndex(a => a == 2); List subList = new List(list); subList[idx] = 1; bool ret = IsWin(subList.OrderBy(a => a).ToList()); if (!ret) { canWin = true; } if (!canWin) { subList = new List(list); subList.RemoveAt(idx); ret = IsWin(subList); if (!ret) { canWin = true; } } } if ((!canWin) && list.Any(a => a == 1)) { idx = list.FindIndex(a => a == 1); List subList = new List(list); subList.RemoveAt(idx); bool ret = IsWin(subList); if (!ret) { canWin = true; } } dic[key] = canWin; return canWin; } private int[] PrimeList; public class Reader { private static StringReader sr; public static bool IsDebug = false; public static string ReadLine() { if (IsDebug) { if (sr == null) { sr = new StringReader(InputText.Trim()); } return sr.ReadLine(); } else { return Console.ReadLine(); } } private static string InputText = @" 100000000 "; } public static void Main(string[] args) { #if DEBUG Reader.IsDebug = true; #endif Program prg = new Program(); prg.Proc(); } }