AOJ2049 Headstrong Student

問題リンク Headstrong Student

• 概要

整数x, yが与えられる。x/yを計算した結果で、循環に入るまでの長さと循環の長さをそれぞれ答えよ。有限小数となるならば循環の長さは0とせよ。
1 <= x < y < 10^6

• 解法

循環に陥るかどうかはx/yの計算途中ででてくる値を覚えておけば分かります。あとは、その値が何度めの除算で出現したかを覚えておけば答えの長さが計算できます。y < 10^6なので、配列で覚えておくことができます。

• ソース

import java.util.Arrays;
import java.util.Scanner;

//Headstrong Student
public class AOJ2049 {

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int x = sc.nextInt(), y = sc.nextInt();
			if((x|y)==0)break;
			int[] a = new int[y];
			Arrays.fill(a, -1);
			a[x] = 0;
			int p = 0, q = 0, r = 1;
			for(;;){
				x = (x*10)%y;
				if(x==0){
					p = r; break;
				}
				if(a[x]==-1){
					a[x] = r++;
				}
				else{
					p = a[x]; q = r-a[x]; break;
				}
			}
			System.out.println(p+" "+q);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2049().run();
	}
}