yukicoder : No.25 有限小数

こちらの方はだいぶ簡単。
http://yukicoder.me/problems/70

問題

整数N,Mが与えられる。
N/Mが整数または有限小数なら、0じゃない最低位の桁の値を答えよ。
有限小数でないなら-1を答えよ。

解法

N/Mが整数なら、1の位が非0になるまでN/Mを10で割り続けるだけ。

以後N/Mが非整数の場合を前提する。
まずNとMを最大公約数で割っておく。

Mを素因数分解し、2と5の指数及び他の素因数を求める。
2と5以外の素因数がある場合、循環小数になるので-1を返す。

2の指数の方が多い場合、その差分だけ2で割る代わりに10/2を掛けると考え、Nを5倍する。
逆に5の指数の方が多い場合、その差分だけ5で割る代わりに10/5を掛けると考え、Nを2倍する。
その際、１の位が0になるなら適宜Nを10で割っていけば良い。

ll N,M;
int M2,M5;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	ll g=__gcd(N,M);
	N/=g;
	M/=g;
	if(N%M==0) {
		N/=M;
		while(N%10==0) N/=10;
		return _P("%lld\n",N%10);
	}
	N%=M;
	
	while(M%2==0) M2++, M/=2;
	while(M%5==0) M5++, M/=5;
	if(M!=1) return _P("-1\n");
	
	while(M2<M5) {
		M2++;
		N*=2;
		N%=1000000000;
		while(N%10==0) N/=10;
	}
	while(M2>M5) {
		M5++;
		N*=5;
		N%=1000000000;
		while(N%10==0) N/=10;
	}
	_P("%lld\n",N%10);
}

まとめ

10進数以外だとまた面白そう。