Poj Solution 3720

http://poj.org/problem?id=3720


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

/**
 * @author Administrator ѭ��С��+ѭ����
 */
public class Main {
    /**
     *����
     */
    private int numerator;
    /**
     *��ĸ
     */
    private int denominator;
    /**
     * ѭ���ڲ��ᳬ��100�����
     */
    private static int MAX_NUM = 101;

    /**
     * @return��ȡС����ʽ���㵽ѭ����+ѭ���ڴ�С ������numerator>=denominator�����;ֻ���������
     */
    private class Node {
        private boolean RemainFlag[];

        private int RemainPreFlag[];

        public boolean[] getRemainFlag() {
            return RemainFlag;
        }

        public void setRemainFlag(boolean[] remainFlag) {
            RemainFlag = remainFlag;
        }

        public int[] getRemainPreFlag() {
            return RemainPreFlag;
        }

        public void setRemainPreFlag(int[] remainPreFlag) {
            RemainPreFlag = remainPreFlag;
        }

    }

    private class Result {

        private int result[];

        private int size;

        public int[] getResult() {
            return result;
        }

        public void setResult(int[] result) {
            this.result = result;
        }

        public int getSize() {
            return size;
        }

        public void setSize(int size) {
            this.size = size;
        }

    }

    public Result getRepeatingPresentation(int numerator, int denominator) {

        int gcd = getGCD(numerator, denominator);
        numerator /= gcd;
        denominator /= gcd; // ���������ʽ
        Result res = new Result();
        res.result = new int[MAX_NUM];
        int remain;
        Node node = new Node();
        node.RemainFlag = new boolean[MAX_NUM];
        node.RemainPreFlag = new int[MAX_NUM];
        for (int i = 0; i < MAX_NUM; i++) {
            node.RemainFlag[i] = false;
            node.RemainPreFlag[i] = 0;
        }
        remain = numerator;
        int i = 0;
        while (true) {
            int tmp = remain * 10 % denominator; // ����
            if (true == node.RemainFlag[tmp]
                    && node.RemainPreFlag[tmp] == remain) {
                break;
            }
            node.RemainFlag[tmp] = true;
            node.RemainPreFlag[tmp] = remain;
            res.result[i] = remain * 10 / denominator; // ��
            remain = remain * 10 % denominator; // ����
            //System.out.print(res.result[i]);
            res.size = i;
            i++;
            if (tmp == 0)
                break;

        }
        return res;

    }

    /**
     * @param a
     * @param b
     * @return ���Լ��+շת���
     */
    public int getGCD(int a, int b) {
        if (a % b == 0)
            return b;
        else
            return getGCD(b, a % b);
    }

    public static void main(String[] args) throws IOException {
        Main t = new Main();
        // t.getRepeatingPresentation(1,6);
        BufferedReader stdin = new BufferedReader(new InputStreamReader(
                System.in));

        while (true) {
            String line = stdin.readLine();
            if(line==null) break;
            StringTokenizer st = new StringTokenizer(line);
            String a1 = st.nextToken();
            String b1 = st.nextToken();
            int a = Integer.parseInt(a1);
            int b = Integer.parseInt(b1);
            Result res[] = new Result[a + 1];
            for (int i = 2; i <= a; i++) {
                res[i] = t.getRepeatingPresentation(1, i);
                //System.out.println();
            }
            int sum = 0;
            for (int i = 2; i <= a; i++) {
                for (int j = 0; j <= res[i].size; j++) {
                    if (res[i].result[j] == b)
                        sum++;
                }
            }
            System.out.println(sum);
        }

    }

    public int getNumerator() {
        return numerator;
    }

    public void setNumerator(int numerator) {
        this.numerator = numerator;
    }

    public int getDenominator() {
        return denominator;
    }

    public void setDenominator(int denominator) {
        this.denominator = denominator;
    }

}