はまやんはまやんはまやん

hamayanhamayan's blog

Position in Fraction [Codeforces Round #450 B]

http://codeforces.com/contest/900/problem/B

分数a/bを割った時に小数部分に初めて数cが出てくるのは小数点以下第何位か。
もし出てこないなら-1

解法

http://codeforces.com/contest/900/submission/33113488

この解法は雰囲気解法で、まだpretest passedの段階なので、記事が消える可能性があります。
 
コドフォのB問題であるということを念頭になるべく簡単に解けないか考えてみる。
普通に割ってcが初めて出てくるのを探せば良さそう。
doubleなどで計算すると誤差が起こるので、自前で筆算のコードを書く。
A≧Bの場合は整数部が出て来るので、それを消すためにA = A % Bとしておく。
筆算するので、残っている数を10倍してBで割っていけばいい。
どこまでやるかであるが、10^5くらいまで探して無ければ循環小数で出てこないだろうという予想で、10^5くらいまで回している(未証明)

int A, B, C;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B >> C;
    A %= B;
    int ans = -1;
    rep(i, 1, 101010) {
        A *= 10;
        if (A / B == C) {
            ans = i;
            break;
        }

        A %= B;
    }
    cout << ans << endl;
}