yukicoder No.25 有限小数

最初の方針
既約分数を小数表示したとき有限小数になるためには、分母が2,5のみを因数に持つことが必要十分
約分をして、分母を10ベキの形に持っていく

long gcd(long a,long b){return b?gcd(b,a%b):a;}
int main(){
	long n,m,t;
	scanf("%ld%ld",&n,&m);
	t=gcd(n,m);
	n/=t;m/=t;
	//約分
	while(n%10<1)n/=10;
	while(m%10<1)m/=10;
	//10の因子を除く
	n%=10;
	//分子は一の位の情報だけあれば十分
	//下の2つのwhile文は、実際にはどちらか一方しか実行されない
	//（mは10の因子を持たないので、2と5の高々一方でしか割れない）
	while(m%2<1){m/=2;n*=5;n%=10;}
	//分母に2の因子があれば「分子分母に5を掛けて分母の10の因子を除く」
	//これは「分子に5を掛けて分母を2で割る」と同じ
	//n,mは互いに素になっているので、ここが実行されるならnは2の因子を持たず、*5%10を計算して大丈夫
	while(m%5<1){m/=5;n*=2;n%=10;}
	//分母に2の因子があれば「分子分母に2を掛けて分母の10の因子を除く」
	//これは「分子に2を掛けて分母を5で割る」と同じ
	//n,mは互いに素になっているので、ここが実行されるならnは5の因子を持たず、*2%10を計算して大丈夫
	if(m!=1)puts("-1");
	//もしmが1でなければ、既約分数の分母mが2,5以外の因数を持っているので有限小数でない
	else printf("%d",n);
	//そうでないならn/1の形になっているので、最下位はn
	return 0;
}

この方針で縮めてみたのがこれ

long a,b,p,q,t;
main(){
	scanf("%ld%ld",&a,&b);
	for(p=a,t=b;q=t;p=q)t=p%q;
	//互除法
	for(a/=p;a%(q=10)<1;a/=q);
	for(b/=p;b%q<1;b/=q);
	//10の除去
	for(t=b%2*3+2;b%t<1;a=a*2%q)b/=t;
	//分母は2ベキか5ベキでしょ
	a=!printf("%d",b-1?-1:t-2?a%q:5);
}

長い
実際に約分しなくても「分母にある2,5の因数以外は分子と約分できる」ことさえ確かめればいいので
とりあえず2,5の因数とそれ以外を分離する

int main(){
	long n,m;
	int n2=0,n5=0,m2=0,m5=0;
	scanf("%ld%ld",&n,&m);
	while(n%2<1){n/=2;n2++;}
	while(n%5<1){n/=5;n5++;}
	while(m%2<1){m/=2;m2++;}
	while(m%5<1){m/=5;m5++;}
	//分子分母の2,5の因数をカウント
	if(n%m!=0){puts("-1");return 0}
	//分母に残ったものが分子で約分できないならダメ
	while(m2--)n5++;
	while(m5--)n2++;
	//先ほどと同じ処理

	//分子にある2と5の因数の数が…
	if(n5>n2)puts("5");
	//5の方が大きければ、結局5の倍数になるので一の位は5
	else if(n5==n2)printf("%d",n/m%10);
	//同じなら10ベキで消えるのでn/mがそのまま出てくる
	else printf("%d",(n/m%10<<(n2-n5)%4+4)%10);
	//2の方が大きければ、2^5≡2 mod10 なので、2の指数はmod4で見れば良い
	//ただし2^4≠2^0 mod10 に注意
	return 0;
}

むしろ長くなった！

でも

while(n%2<1){n/=2;n2++;}
while(n%5<1){n/=5;n5++;}
while(m%2<1){m/=2;m2++;}
while(m%5<1){m/=5;m5++;}
while(m2--)n5++;
while(m5--)n2++;

は

while(n%2<1){n/=2;n2++;}
while(n%5<1){n/=5;n5++;}
while(m%2<1){m/=2;n5++;}
while(m%5<1){m/=5;n2++;}

にまとめられる。さらに
今までは(2^n2)*(5^n5)*n/mと見ていたが、これを
(2^n2)*10^hoge*n/mと見れば

while(n%2<1){n/=2;n2++;}
while(n%5<1){n/=5;n2--;}
while(m%2<1){m/=2;n2--;}
while(m%5<1){m/=5;n2++;}

で十分
n2が負になっても、結局分子に10^4のベキをかけたと考えれば以降の処理に問題はない

long n,m;t;
main(){
	scanf("%ld%ld",&n,&m);
	for(;n%2<1;t++)n/=2;
	for(;n%5<1;t--)n/=5;
	for(;m%2<1;t--)m/=2;
	for(;m%5<1;t++)m/=5;
	t=!printf("%d",n%m?-1:t<0?5:t?(n/m%10<<t%4+4)%10:n/m%10);
}

n,mに対して似たような処理をしてるのでまとめたい
forだと値の受け渡しがうまく咬み合わなかったのでmain再帰

long n,m;t;
main(i){
	scanf("%ld",&m);
	for(;m%2<1;t+=i)m/=2;
	for(;m%5<1;t-=i)m/=5;
	n?t=!printf("%d",n%m?-1:t<0?5:n/m%10*(t?1<<t%4+4:1)%10):main(-1,n=m);
}

最後にm%2<1を~m%2に書き換えて

long n,m;t;
main(i){
	for(scanf("%ld",&m);~m%2;t+=i)m/=2;
	for(;m%5<1;t-=i)m/=5;
	n?t=!printf("%d",n%m?-1:t<0?5:n/m%10*(t?1<<t%4+4:1)%10):main(-1,n=m);
}

145B

メモ

yukicoderでゆるふわgolf

yukicoder No.25 有限小数