linux畅想

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