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; } }