Round 107 Div2 C Win or freeze

codefoces program

問題

  • Win or Freeze
    • 交互に手番が来る2人ゲーム
    • 紙に自然数 q が最初に書かれている
    • 手番のプレイヤーは紙に最後に書かれた数字の非自明な約数を書かなければならない
    • 何も書くことが出来なくなったプレイヤーの勝ち

方針

q を q = p1 x p2 x p3 x ... x pn と素因数分解したとする

  • n = 1
    • いきなり先手の勝ち
  • n = 2
    • 先手は p1 or p2 を紙に書かなければならず、後手の勝ち
  • n = 3
    • p1 x p2 を書けば先手の勝ち

となる。実際にはqを完全に素因数分解する必要はなくて、高々2個の素因数を見つければ良い。

コード

/*! g++ -O3 c2.cpp
 */

#include <vector>
#include <iostream>
#include <list>
#include <cmath>
#include <algorithm>
#include <iterator>



using namespace std;

typedef unsigned long long ull;

void try_divide(ull n, ull& d){
  for(d = 2; d <= sqrt((double)n); d++){
    if(n % d == 0) return;
  }
  d = 0;
}

int main(int argc, char *argv[]){
  ull q;
  cin >> q;


  ull d1;
  try_divide(q, d1);
  if(d1 == 0){
    cout << 1 << endl
	 << 0 << endl;
    return 0;
  }

  ull d2;
  try_divide(q / d1, d2);
  if(d2 == 0){
    cout << 2 << endl;
    return 0;
  }

  cout << 1 << endl
       << (d1 * d2) << endl;
  return 0;
}