tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

SRM 517 Div1

よくわからないのに参加。りんごさんがwriterと予想したらやっぱり当たった。

250:Chad
Prime Smashの問題。りんごさんこれにはまったのだろうか。
数学をする。aなんたらを互いに異なる素数とする。
N=targetならYes,N%target!=0ならNoはあらかじめ処理しておく。

N=a1^b1*a2^b2とすると、
a1^2はNからa1だけを切り出し続けていくと出てこない。(a1^b1*a2^b2 → a1^(b1-1)*a2^b2 → a1^(b1-2)*a2^b2 → … → a1*a2^b2 → a2^b2と切り出すとa1^2は出てこない)、a2^2も同様。もちろんそれらにa1やa2をかけたものも切り出せない。
a1*a2も出てこないことがある。(a1^b1*a2^b2をa1^b1とa2^b2に切る)
さすがにa1やa2は必ず出てくる。

別にこれはa1^b1*a2^b2*a3^b3*…でもいえる。

N=a^bとする(素数の累乗)。
a^bからaは当然出てくる。
a^2を作ることも必ず出来る。これはb=2なら当然だし、b=3のときは切ったらaとa^2になるし、b=4のときは切ったらa^2とa^2かaとa^3となるし… と数学的帰納法で証明できる。
a^3は作ることが出来ない。というのもa^bから1と2を使えば3は避けられるからである(2を使って一つ指数をとばす)、4以上も同様である。

よって、
N=a1^b1*a2^b2*a3^b3*…のときtargetがa1,a2,a3…ならYes
N=a^b(↑のが1個しかないパターン)のときtargetがaまたはa^2ならYesである。

こんなことしなくても探索すればすぐである。

public class CompositeSmash{
	public String thePossible(int a,int b){
		if(a==b)return "Yes";
		int c=a;
		int type=0;
		for(int i=2;i<=a;i++){
			int add=0;
			while(c%i==0){
				c/=i;
				add=1;
			}
			type+=add;
		}
		if(type==1){
			if(a%b!=0)return "No";
			boolean ok=false;
			boolean val=true;
			for(int i=2;i*i<=b;i++){
				if(b%i==0)val=false;
			}
			if(val)ok=true;
			int e=-1;
			for(int i=0;i*i<=b;i++)if(i*i==b)e=i;
			if(e!=-1){
				val=true;
				for(int i=2;i*i<=e;i++){
					if(e%i==0)val=false;
				}
				if(val)ok=true;
			}
			if(ok)return "Yes";
			else return "No";
		}else{
			if(a%b!=0)return "No";
			for(int i=2;i*i<=b;i++){
				if(b%i==0)return "No";
			}
			return "Yes";
		}
	}
}

600:Matthew
左からみてここからここまで動かすのを求めて数学して同じことを右からみて数学すると求まると思ったのですがどうやら違うらしい(手でやったら合わなかった)

900:Colm
鑑賞しました。

Sothe Phase:
どうみてもChallengeゲーなのに落とせないとか緑風未満。

Volke Test:
(なぜか)通った

Result:
208.94 + 0 + 0 + 0 = 208.94 (239th)
Rating:
1612 -> 1670 (-INF)

レートが上がっているように見えた人は病院にいくといいかもしれません。