Codeforces #107 (Div.1)

コンテスト中に書いたメモをアップしてみる．

A. Win or Freeze

最初のプレーヤーをA，次のプレーヤーをBとする．qの自明でない約数が存在しない時はAの勝ち（1 or 素数）．それ以外の時は，qの自明でない約数でかつ，自身の自明でない約数が素数のみとなるような数をBに与えたい．例えば，Aに30が与えられたら，6，10，15をBに与えればAが勝つ．従って，qを素因数分解し指数の総和を見れば，勝敗を判定することが出来る．

long q;
void run(){
	q=sc.nextLong();
	solve();
}
void solve(){
	HashMap<Long, Integer> map=pf(q);
	int sum=0;
	for(Entry<Long, Integer> entry : map.entrySet()){
		sum+=entry.getValue();
	}
	if(sum==0||sum==1){
		println("1\n0");
	}else if(sum==2){
		println("2");
	}else{
		long n=1;
		sum=0;
		for(Entry<Long, Integer> entry : map.entrySet()){
			for(int i=0; i<entry.getValue()&&sum<2; i++, sum++){
				n*=entry.getKey();
			}
			if(sum==2){
				break;
			}
		}
		println("1");
		println(""+n);
	}
}
HashMap<Long, Integer> pf(long n){
	HashMap<Long, Integer> map=new HashMap<Long, Integer>();
	for(long i=2; i*i<=n; i++){
		int c=0;
		for(; n%i==0; n/=i){
			c++;
		}
		if(c>0){
			map.put(i, c);
		}
	}
	if(n!=1){
		map.put(n, 1);
	}
	return map;
}

B. Quantity of Strings

いくつかのパターンを試すと，どこが同じでどこが同じでなくてもよいか，という自由度の規則性が出てくる．ちなみに，Union-Find等を用いて自由度を計算することも出来る．

int mod=(int)1e9+7;
int n, m, k;
void run(){
	n=sc.nextInt();
	m=sc.nextInt();
	k=sc.nextInt();
	solve();
}
void solve(){
	long ans;
	if(k==1){
		ans=powMod(m, n);
	}else if(k%2==0){
		if(n>k){
			ans=m;
		}else if(n==k){
			ans=powMod(m, k/2);
		}else{
			ans=powMod(m, n);
		}
	}else{
		if(n>k){
			ans=m*m%mod;
		}else if(n==k){
			ans=powMod(m, (k+1)/2);
		}else{
			ans=powMod(m, n);
		}
	}
	println(ans+"");
}
long powMod(long x, int k){
	if(k==0)
		return 1;
	if(k%2==0)
		return powMod(x*x%mod, k>>1);
	else
		return x*powMod(x, k-1)%mod;
}

結果

oo--- 876pts. 139th
1926 -> 1981