Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Japan 2011 決勝 B問題 - バクテリアの増殖 (この記事を編集する[管理者用])

Source

Google Code Jam Japan 2011 決勝 B問題

問題概要

問題分が日本語なので略.

解法

x^x mod zを考えるとき,基本的にyが大きくなると,yについて周期phi(z)に落ち込む.
なので,x mod zとx mod phi(z)があればいい.
ただし,phiはオイラーのファイ関数.
時刻n後のバクテリアの数をf(n)として,
1以上C以下の整数xについて,f(n) mod xの値と,f(n)がxより大きいかどうかを覚えておく.

Cによるスパゲッティなソースコード
#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 EulerPhiEasy(int n){
  int i,k,ret=n;
  for(i=2;i*i<=n;i++) if(n%i==0){
    while(n%i==0) n/=i;
    ret = ret/i*(i-1);
  }
  if(n>1) ret = ret/n*(n-1);
  return ret;
}

ll pw(ll a,ll b, ll md, int *fg){
  ll r;
  if(!b) return 1;
  r = pw(a,b/2,md,fg);
  r = r*r;
  if(r >= md){
    r %= md;
    *fg = 1;
  }
  if(b%2){
    r = r*a;
    if(r >= md){
      r %= md;
      *fg = 1;
    }
  }
  return r;
}

ll phi[2000];
ll md[2000], next[2000];
int now_fg[2000], next_fg[2000];


int main(){
  int i,j,k,l,m,n,fg,loop;
  int res;
  int size, count=0;
  ll A, B, C;

  REP(i,1,2000) phi[i] = EulerPhiEasy(i);

  scanf("%d",&size);
  while(size--){
    fprintf(stderr,"size %d\n",size);
    scanf("%lld%lld%lld",&A,&B,&C);

    REP(i,1,C+1){
      md[i] = A%(2*i);
      now_fg[i] = 0;
      if(A >= (2*i)) now_fg[i] = 1;
/*      printf("-1: %d %lld %d\n",i,md[i],now_fg[i]);*/
    }
    rep(loop,B){
      REP(i,1,C+1){
        m = md[phi[i]];
        if(now_fg[phi[i]]) m += phi[i]*2;

        fg = 0;
        next[i] = pw(md[i], m, (2*i), &fg);
        next_fg[i] = fg;
        if(now_fg[i]) next_fg[i] = 1;
      }
      REP(i,1,C+1){
        md[i] = next[i];
        now_fg[i] = next_fg[i];
/*        printf("%2d: %d %lld %d\n",loop,i,md[i],now_fg[i]);*/
      }
    }

    res = md[C] % C;

    printf("Case #%d: %d\n",++count,res);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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