PKU : 3720 - Occurrence of Digits

問題概要

http://poj.org/problem?id=3720
1/2 = .5, 1/3 = .(3), 1/6 = .1(6)...
であるとき, 1/2〜1/nの小数点以下に数字kが何回出現するか求めよ.

アルゴリズム

ひっ算をやる感じで, 愚直に解く.

プログラム

bool flg[10000];

int solve(int n,int k){
  int res = 0;
  int rem = 10;

  memset(flg,0,sizeof(flg));
  flg[0] = true;

  while(!flg[rem]){
    flg[rem] = true;
    int div = rem / n;
    if(div == k) res++;
    rem -= div * n;
    rem *= 10;
  }

  return res;
}

int main(void){
  int n,k;

  while(cin>>n>>k){
    int res = 0;
    for(int i=2;i<=n;i++){
      res += solve(i,k);
    }
    cout<<res<<endl;
  }
}