Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /** Team Proof
- Java template
- */
- import java.io.*;
- import java.util.*;
- import java.math.*;
- public class Main
- {
- BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
- StringTokenizer tokenizer=null;
- public static void main(String[] args) throws IOException
- {
- new Main().execute();
- }
- void debug(Object...os)
- {
- System.out.println(Arrays.deepToString(os));
- }
- int ni() throws IOException
- {
- return Integer.parseInt(ns());
- }
- long nl() throws IOException
- {
- return Long.parseLong(ns());
- }
- double nd() throws IOException
- {
- return Double.parseDouble(ns());
- }
- String ns() throws IOException
- {
- while (tokenizer == null || !tokenizer.hasMoreTokens())
- tokenizer = new StringTokenizer(br.readLine());
- return tokenizer.nextToken();
- }
- String nline() throws IOException
- {
- tokenizer=null;
- return br.readLine();
- }
- //Main Code starts Here
- int totalCases, testNum;
- BigInteger g,x,y;
- void extgcd(BigInteger a,BigInteger b)
- {
- if(b.equals(BigInteger.ZERO))
- {
- g=a;
- x=BigInteger.ONE;
- y=BigInteger.ZERO;
- }
- else
- {
- BigInteger div = a.divide(b);
- extgcd(b,a.subtract(b.multiply(div)));
- BigInteger temp=x;
- x=y;
- y=temp.subtract((div).multiply(y));
- }
- }
- BigInteger CRT(BigInteger a1,BigInteger m1,BigInteger a2,BigInteger m2)
- {
- extgcd(m1,m2);
- BigInteger t1 = a2.multiply(x).multiply(m1);
- BigInteger t2 = a1.multiply(y).multiply(m2);
- return (t1.add(t2)).mod(m1.multiply(m2));
- }
- void execute() throws IOException
- {
- preprocess();
- totalCases = ni();
- for(testNum = 1; testNum <= totalCases; testNum++)
- {
- if(!input())
- break;
- solve();
- }
- }
- int N;
- BigInteger[] a1=new BigInteger[505];
- BigInteger[] a2=new BigInteger[505];
- BigInteger two,five;
- BigInteger pow2,pow5;
- void preprocess()
- {
- two=BigInteger.valueOf(2);
- five=BigInteger.valueOf(5);
- pow2=two;
- pow5=five;
- for(int i=2;i<=500;i++)
- {
- pow2=pow2.multiply(two);
- pow5=pow5.multiply(five);
- a1[i] = CRT(BigInteger.ONE, pow2, BigInteger.ZERO, pow5);
- a2[i] = CRT(BigInteger.ZERO, pow2, BigInteger.ONE, pow5);
- }
- }
- void solve()
- {
- if(N==1)
- {
- System.out.println("Case #"+testNum+": 0 1 5 6");
- return;
- }
- if(a1[N].compareTo(a2[N]) < 0)
- System.out.println("Case #"+testNum+": "+a1[N].toString()+" "+a2[N].toString());
- else
- System.out.println("Case #"+testNum+": "+a2[N].toString()+" "+a1[N].toString());
- }
- boolean input() throws IOException
- {
- N=ni();
- return true;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement