Codeforces #174 Div2. A. Cows and Primitive Roots, B. Cows and Poker Game

CF174は不参加だけど、順々に復習。
http://codeforces.com/contest/284/problem/A
http://codeforces.com/contest/284/problem/B

A. Cows and Primitive Roots

2000以下の素数pが与えられるので、1～(p-1)の数xのうち、x-1,x^2-1,...,x^(p-2)-1がpで割り切れず、x^(p-1)-1がpで割り切れる数の個数を答える。

フェルマーの小定理より、x^(p-1)-1がpで割り切れるのは明らか。
あとは実際に各xについてx^(p-2) % pが1にならないことを実際に計算すればよい。
計算量はO(p^2)だがpが小さいので問題ない。

void solve() {
	int p;
	int i,j,k,res=0;
	
	p=GETi();
	for(i=1;i<p;i++) {
		j=1;
		int ng=0;
		FOR(k,p-2) {
			j=(j*i)%p;
			if(j==1) ng=1;
		}
		if(!ng) res++;
	}
	
	_P("%d\n",res);
	return;
}

B. Cows and Poker Game

N人の人がポーカーをプレイしている。
N人の状態がA・I・Fの時、AまたはIの人は手をオープンすることができる。
ただし、各人は他人がAまたはFの時しかオープンしない。
各人の状態が与えられたとき、手をオープンする人数を答える。

問題文がややこしいがやってることは単純。

• Iが２人以上いたら誰もオープン出来ない。
• Iが1人いたら、その人だけオープンする。
• Iが0人なら、Aの人は全員オープンする。

int N;
char S[200002];
int C[256];

void solve() {
	int f,r,i,j,k,l,x,y,cur,tar;
	
	N=GETi();
	GETs(S);
	FOR(i,N) C[S[i]]++;
	
	if(C['I']>=2) _P("0\n");
	else if(C['I']>=1) _P("1\n");
	else _P("%d\n",C['A']);
	
	return;
}

まとめ

Bの問題、プログラムより文章を読んで論理を組み立てる問題に見えるな…。