http://acm.hdu.edu.cn/showproblem.php?pid=2117
Problem Description
Now give you two integers n m, you just tell me the m-th number after radix point in 1/n,for example n=4,the first numble after point is 2,the second is 5,and all 0 followed.
Input
Each line of input will contain a pair of integers for n and m(1<=n<=10^7,1<=m<=10^5).
Output
For each line of input, your program should print a numble on a line,according to the above rules.
Sample Input
4 2
5 7
123 123
Sample Output
5
0
8
代码
#include<stdio.h> __int64 solve(int m,int n) { __int64 t; if(n==0) return 1; if(n==1) return 10%m; t=solve(m,n/2); t*=t; if(n%2==1) t*=10%m; return t%m; } void main() { int n,m; while(scanf("%d%d",&m,&n)!=EOF) printf("%I64d\n",((10*solve(m,n-1))/m)%10); }
对于输入m,n
则有1/m=0.xxxx…xxxaxxx
其中a为小数点后第n位即所求的答案
接下来a=(10^n/m)%10;
存在b,c使得10^n=m*b*10+c (其中c=(10^n)%(10*m)=10*(10^(n-1))%m即c<10*m);
所以a=((m*b*10+c)/m)%10=(b*10+c/m)%10=(c/m)%10=c/m;
这个过程中只要求c就能求出a=c/m;
而c=10*(10^(n-1))%m这个可用二分递归求解如程序中的10*solve(m,n-1))
所以a=(10*solve(m,n-1))/m;保险起见我当初加了个”%10″;
0 条评论。