2013
11-13

# Occurrence of Digits

Every fraction can be converted to a repeatin decimal. For example 1/2 = .5, 1/3 = .(3) and 1/6 = .1(6). Given an integer n, Tom wants to know how many digit k occurs totally in the repeating decimal presentation of 1/2, 1/3 … 1/n.

The input consists of several test cases. Each test case is a line containing two integers n (2 ≤ n ≤ 100) and k (0 ≤ k ≤ 9).

Output the total occurrence of the digit.

3 5
7 3
7 0


1
1
0

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

/**
*/
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);
System.in));

while (true) {
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;
}

}

1. 很高兴你会喜欢这个网站。目前还没有一个开发团队，网站是我一个人在维护，都是用的开源系统，也没有太多需要开发的部分，主要是内容整理。非常感谢你的关注。

2. 第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。