POJ 1930 Dead Fraction

POJ 1930 Dead Rraction

　　此题是一个将无限循环小数转化为分数的题目

　　对于一个数 x=0.abcdefdef....

　　假设其不循环部分的长度为m（如abc的长度为m），循环节的长度为n（def的长度为n）,此时的主要目的是消除后面的循环部分，

　　x*10^(m+n)=abcdef.defdef...

　　 x*10^n= abc.defdef..

　　　　通过比较两式，做减法可消除循环部分·

　　　　x*10^n*(10^m-1)=abcdef-abc（整数）

　　　　　x=(abcdef-abc)/(10^(m+n)-10^n);

　　　　　设 s=abcdef-abc,t=10^(m+n)-10^n;

　　　　　　此题转化为求h=gcd(s,t);

　　　　　　最后x=(s/h)/(t/h) 即为所求不可约分数

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <string>

#include <cmath>

using namespace std;

const int INF=0x3f3f3f3f;

typedef long long ll;

int gcd(int n,int m)//求最大公约数

{

    if(m==) return n; //n%m==0(n与m的余数为0)

    return gcd(m,n%m);(n是大数,m是小数)

}

int main()

{

    int all,num,l,m,n,a,b,k,mis,mns;

    char str[];

    while(gets(str)&&strcmp(str,""))

    {

        l=;all=;mis=INF;

        for(int i=;str[i]!='.';i++)

        {

            all=all*+str[i]-;

            l++;

        }

        num=all;

        for(int j=;j<=l;j++)

        {

            num=num/;

            a=all-num;

            b=(int)pow(,l-j)*(pow(,j)-);

            k=gcd(b,a);

            if(b/k<mis)

            {

                mns=a/k;

                mis=b/k;

            }

        }

        printf("%d/%d\n",mns,mis);

    }

    return ;

}

巴特西

POJ 1930 Dead Fraction

最新文章

热门文章