Advertisement
Guest User

Untitled

a guest
Aug 17th, 2017
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.60 KB | None | 0 0
  1. /** Team Proof
  2. Java template
  3. */
  4.  
  5. import java.io.*;
  6. import java.util.*;
  7. import java.math.*;
  8.  
  9. public class Main
  10. {
  11.     BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  12.     StringTokenizer tokenizer=null;
  13.    
  14.     public static void main(String[] args) throws IOException
  15.     {
  16.         new Main().execute();
  17.     }
  18.    
  19.     void debug(Object...os)
  20.     {
  21.         System.out.println(Arrays.deepToString(os));
  22.     }
  23.    
  24.     int ni() throws IOException
  25.     {
  26.         return Integer.parseInt(ns());
  27.     }
  28.    
  29.     long nl() throws IOException
  30.     {
  31.         return Long.parseLong(ns());
  32.     }
  33.    
  34.     double nd() throws IOException
  35.     {
  36.         return Double.parseDouble(ns());
  37.     }
  38.        
  39.     String ns() throws IOException
  40.     {
  41.         while (tokenizer == null || !tokenizer.hasMoreTokens())
  42.             tokenizer = new StringTokenizer(br.readLine());
  43.         return tokenizer.nextToken();
  44.     }
  45.    
  46.     String nline() throws IOException
  47.     {
  48.         tokenizer=null;
  49.         return br.readLine();
  50.     }
  51.        
  52.    
  53.  
  54.     //Main Code starts Here
  55.     int totalCases, testNum;   
  56.    
  57.  
  58.    
  59.     BigInteger g,x,y;
  60.     void extgcd(BigInteger a,BigInteger b)
  61.     {
  62.         if(b.equals(BigInteger.ZERO))
  63.         {
  64.             g=a;
  65.             x=BigInteger.ONE;
  66.             y=BigInteger.ZERO;
  67.         }
  68.         else
  69.         {
  70.             BigInteger div = a.divide(b);
  71.             extgcd(b,a.subtract(b.multiply(div)));
  72.             BigInteger temp=x;
  73.             x=y;
  74.             y=temp.subtract((div).multiply(y));
  75.         }
  76.     }
  77.    
  78.     BigInteger CRT(BigInteger a1,BigInteger m1,BigInteger a2,BigInteger m2)
  79.     {
  80.         extgcd(m1,m2);
  81.         BigInteger t1 = a2.multiply(x).multiply(m1);
  82.         BigInteger t2 = a1.multiply(y).multiply(m2);
  83.  
  84.         return (t1.add(t2)).mod(m1.multiply(m2));
  85.     }
  86.    
  87.  
  88.     void execute() throws IOException
  89.     {
  90.         preprocess();
  91.         totalCases = ni();
  92.         for(testNum = 1; testNum <= totalCases; testNum++)
  93.         {
  94.             if(!input())
  95.                 break;
  96.             solve();
  97.         }
  98.     }
  99.    
  100.     int N;
  101.     BigInteger[] a1=new BigInteger[505];
  102.     BigInteger[] a2=new BigInteger[505];
  103.     BigInteger two,five;
  104.     BigInteger pow2,pow5;
  105.    
  106.    
  107.     void preprocess()
  108.     {
  109.         two=BigInteger.valueOf(2);
  110.         five=BigInteger.valueOf(5);
  111.         pow2=two;
  112.         pow5=five;
  113.        
  114.         for(int i=2;i<=500;i++)
  115.         {
  116.             pow2=pow2.multiply(two);
  117.             pow5=pow5.multiply(five);
  118.             a1[i] = CRT(BigInteger.ONE, pow2, BigInteger.ZERO, pow5);
  119.             a2[i] = CRT(BigInteger.ZERO, pow2, BigInteger.ONE, pow5);  
  120.         }
  121.     }
  122.        
  123.  
  124.     void solve()
  125.     {
  126.         if(N==1)
  127.         {
  128.             System.out.println("Case #"+testNum+": 0 1 5 6");
  129.             return;
  130.         }
  131.        
  132.         if(a1[N].compareTo(a2[N]) < 0)
  133.             System.out.println("Case #"+testNum+": "+a1[N].toString()+" "+a2[N].toString());
  134.         else
  135.             System.out.println("Case #"+testNum+": "+a2[N].toString()+" "+a1[N].toString());
  136.     }
  137.  
  138.     boolean input() throws IOException
  139.     {
  140.         N=ni();
  141.         return true;
  142.     }
  143.  
  144.  
  145. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement