fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5.  
  6. class Main
  7. {
  8.     static long MOD=1000000;
  9.     static long[][] multiply(long[][] v1) {
  10.         long[][] ans=new long[2][2];
  11.         long x00 = v1[0][0];
  12.         long x01 = v1[0][1];
  13.         long x10 = v1[1][0];
  14.         long x11 = v1[1][1];
  15.         long res00, res01, res10, res11;
  16.         res00 = ((x00 * x00) % MOD + (x10 * x01) % MOD) % MOD;
  17.         res01 = ((x00 * x01) % MOD + (x01 * x11) % MOD) % MOD;
  18.         res10 = ((x10 * x00) % MOD + (x10 * x11) % MOD) % MOD;
  19.         res11 = ((x10 * x01) % MOD + (x11 * x11) % MOD) % MOD;
  20.         ans[0][0]=(res00+MOD)%MOD;
  21.         ans[0][1]=(res01-MOD)%MOD;
  22.         ans[1][0]=(res10+MOD)%MOD;
  23.         ans[1][1]=(res11-MOD)%MOD;
  24.         return ans;
  25.     }
  26.  
  27.     static long[][] pow_mod(long[][] v, int p) {
  28.         if (p == 1) return v;
  29.         //if ((p % 2) == 0)
  30.         return multiply((pow_mod(v, p / 2)));
  31.     }
  32.     public static void main (String[] args)
  33.     {
  34.         Scanner in = new Scanner(System.in);
  35.  
  36.         int t=in.nextInt();
  37.         for (int i = 0; i < t; i++)
  38.         {
  39.             int n=in.nextInt();
  40.             if (n % 3!=0)
  41.             {
  42.                 System.out.println(0);
  43.             }
  44.             else
  45.             {
  46.                 n /= 3;
  47.                 int p = 2;
  48.                 long a1 = 1, a2 = 1;
  49.                 while (n > 0)
  50.                 {
  51.                     if ((n & 1)==1)
  52.                     {
  53.                         long[][] a = { {4,-1},{1,0} };
  54.                         a = pow_mod(a, p / 2);
  55.                         long tmp1 = a1;
  56.                         long tmp2 = a2;
  57.                         a1 = (tmp1 * a[0][0]) % MOD + (tmp2 * ((a[0][1] + MOD) % MOD)) % MOD;
  58.                         a2 = (tmp1 * a[1][0]) % MOD + (tmp2 * ((a[1][1] + MOD) % MOD)) % MOD;
  59.                     }
  60.                     p *= 2;
  61.                     n >>= 1;
  62.                 }
  63.                 a1=a1%MOD;
  64.                 System.out.println(a1);
  65.             }
  66.         }
  67.     }
  68. }
Runtime error #stdin #stdout #stderr 0.1s 35316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.util.NoSuchElementException
	at java.base/java.util.Scanner.throwFor(Scanner.java:937)
	at java.base/java.util.Scanner.next(Scanner.java:1594)
	at java.base/java.util.Scanner.nextInt(Scanner.java:2258)
	at java.base/java.util.Scanner.nextInt(Scanner.java:2212)
	at Main.main(Main.java:36)
https://ideone.com/8LxPJw
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!