Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2232-e4ef87ff
この記事にトラックバックする(FC2ブログユーザー)

Round #107 DIV1 A問題/DIV2 C問題 - Win or Freeze (この記事を編集する[管理者用])

Source

Codeforces Round #107 DIV1 A問題 (500pt)
Codeforces Round #107 DIV2 C問題 (1500pt)
Problem description

問題概要

2人でゲームを行う.行動できなくなったら勝ち.
先手必勝か後手必勝か判定し,もし先手必勝なら最初のターンの勝てる行動を1つ求める問題.
最初正整数 n (10^13以下) が書かれている.
各ターン,書かれている数字を,そのノントリビアルな約数 (1とその数字自体を除く約数) を1つ選んで書き換える.

解法

1または素数なら,すでに行動できないので勝ち.
nが2つの素数の積(同じ素数の積でも良い)なら,どちらかの素数しか選べなく,どっちにしろ負け.
nが3つ以上の素数の積なら,2つの素数の積にできるので勝てる.
1つのゲームで状態数は小さいので,DPしても良い.

C言語のスパゲッティなコード

(本番に書いたコードで多少方針は異なる,2つの素数の積の最小値を探し,そこに動こうとする)

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

int main(){
  ll i,j,k,l,m,n;

  while(scanf("%I64d",&n)==1){
    for(i=2;i*i<=n;i++) if(n%i==0) break;

    if(i*i > n){
      puts("1");
      puts("0");
      continue;
    }

    if(i*i < n && n%(i*i)==0){
      puts("1");
      printf("%I64d\n",i*i);
      continue;
    }

    for(j=i+1;j*j<=n;j++) if(n%j==0) break;
    if(j*j <= n){
      puts("1");
      printf("%I64d\n",i*j);
      continue;
    }

    puts("2");
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2232-e4ef87ff
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。