Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

200题留念,贴代码庆祝,Java写的

Posted by 1000010314 at 2013-01-31 21:07:10 on Problem 1140
import java.io.*;
import java.math.*;
import java.util.*;


public class Main
{
    static Scanner cin=new Scanner(System.in);
    static PrintWriter cout=new PrintWriter(System.out, true);
    static int a,b;

    
    static boolean[] data=new boolean [1100];
    static int[] prime=new int[200];
    
    public static int func1(int n)
    {
        int ans1=0,ans2=0;
        while(n%2==0){ans1++;n/=2;}
        while(n%5==0){ans2++;n/=5;}
        return ans1>ans2?ans1:ans2;
    }
    
    public static int gcd(int x, int y)
    {
        if(x>y){int t=x;x=y;y=t;}
        if(x==0){return y;}
        if(y%x==0||x==0){return x;}
        return gcd(y%x,x);
    }
    
    public static int lcm(int x, int y)
    {
        if(x>y){int t=x;x=y;y=t;}
        return x*y/gcd(x,y);
    }
    
    public static int carmichael(int n)
    {
        int answer=1;
        for(int i=0;n>=prime[i]&&i<168;i++)
        {
            if(n%prime[i]==0)
            {
                answer=lcm(answer,prime[i]-1);
                n/=prime[i];int tmp=1;
                while(n%prime[i]==0)
                {
                    tmp*=prime[i];
                    n/=prime[i];
                }
                answer=lcm(answer,tmp);
            }
        }
        if(n>1){answer=lcm(answer,n-1);}
        return answer;
    }
    
    public static int times(int a,int k,int m)
    {
        if(k==0){return 1;}
        if(k==1){return a%m;}
        if(k%2==0)
        {
            a=(a*a)%m;
            return times(a,k/2,m)%m;
        }
        else
        {
            return (a*times((a*a)%m,k/2,m))%m;
        }
    }
    
    public static void main(String[] args)
    {
        Arrays.fill(data, true);
        data[0]=data[1]=false;
        for(int i=2,k=0;i<1000;i++)
        {
            if(data[i])
            {
                for(int j=2*i;j<1000;j+=i)
                {
                    data[j]=false;
                }
                prime[k++]=i;
            }
        }
        while(cin.hasNext())
        {
            a=cin.nextInt();
            b=cin.nextInt();
            if(a==0&&b==0){return;}
            int tmp=gcd(a,b);
            a=a/tmp;
            b=b/tmp;
            int n1=func1(b),n2,n3=b;
            while(b%2==0){b/=2;}
            while(b%5==0){b/=5;}
            n2=carmichael(b);
            if(b==1)
            {
                BigDecimal x=new BigDecimal(Integer.toString(a));
                BigDecimal y=new BigDecimal(Integer.toString(n3));
                String str=x.divide(y).toString();
                str=str.substring(1,str.length());
                cout.println(str);
                cout.println("This expansion terminates.");
            }
            else
            {
                for(int i=0;i<168;i++)
                {
                    while(n2%prime[i]==0)
                    {
                        n2/=prime[i];
                        if(times(10,n2,b)!=1)
                        {
                            n2*=prime[i];
                            break;
                        }
                    }
                }
                BigDecimal x=new BigDecimal(Integer.toString(a));
                BigDecimal y=new BigDecimal(Integer.toString(n3));
                String str=x.divide(y,n1+n2,BigDecimal.ROUND_DOWN).toString();
                str=str.substring(1,str.length());
                tmp=str.length();
                for(int i=0;i<tmp;i+=50)
                {
                    cout.println(str.substring(i, i+50<tmp ? i+50:tmp));
                }
                cout.println("The last "+Integer.toString(n2)+" digits repeat forever.");
            }
        }
    }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator