fork download
copy 
  1.  
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. class Fast_Modular_Exponentiation {
  8.  
  9.     private int ans = 1;
  10.  
  11.     public int Power(int b, int p, int mod) {
  12.         while (p > 0) {
  13.             if ((p & 1) == 1) {
  14.                 ans = ((ans % mod) * b) % mod;
  15.             }
  16.             b = ((b % mod) * b) % mod;
  17.             p >>= 1;
  18.         }
  19.         return (ans % mod);
  20.     }
  21. }
  22.  
  23. class Extract_Primes {
  24.  
  25.     final private int MAX = 500000;
  26.     public boolean[] arr = new boolean[MAX + 1];
  27.     final private int LIMIT = (int) Math.sqrt(MAX);
  28.     public int[] primes = new int[MAX];
  29.     public int sz = 0;
  30.  
  31.     private void E_primes() {
  32.         for (int i = 2; i <= MAX; i++) {
  33.             if (arr[i] == true) {
  34.                 primes[sz++] = i;
  35.             }
  36.         }
  37.     }
  38.  
  39.     public void Calculate_primes() {
  40.  
  41.         for (int i = 0; i <= MAX; i++) {
  42.             arr[i] = true;
  43.         }
  44.         arr[0] = arr[1] = false;
  45.         for (int i = 2; i <= LIMIT;) {
  46.             if (arr[i] == true) {
  47.                 for (int j = i + i; j <= MAX; j += i) {
  48.                     arr[j] = false;
  49.                 }
  50.             }
  51.             if (i == 2) {
  52.                 i += 1;
  53.             } else {
  54.                 i += 2;
  55.             }
  56.         }
  57.         E_primes();
  58.     }
  59. }
  60.  
  61. class Number_Of_Positive_Factors {
  62.  
  63.     private int cnt = 1;
  64.     private int ans = 1;
  65.  
  66.     public int Factors(int no, Extract_Primes ob) {
  67.         int number = no;
  68.         for (int i = 0; i < ob.sz && (ob.primes[i] <= (int)Math.sqrt(number)); i++) {
  69.             cnt = 1;
  70.             while (number % ob.primes[i] == 0) {
  71.                 cnt++;
  72.                 number /= ob.primes[i];
  73.             }
  74.             ans *= cnt;
  75.         }
  76.         if (number > 1) {
  77.             ans = ans * 2;
  78.         }
  79.         return (ans);
  80.     }
  81. }
  82.  
  83. class Perfect_Numbers_Calculation {
  84.  
  85.     private final int MAX = 500000;
  86.     boolean[] check = new boolean[MAX];
  87.  
  88.     public void Perfect() {
  89.  
  90.         check[0] = false;
  91.         for (int i = 1; i * i <= MAX; i++) {
  92.             check[i * i] = true;
  93.         }
  94.     }
  95. }
  96.  
  97. public class Main {
  98.  
  99.     public static void main(String[] args) {
  100.         InputStream inputstream = System.in;
  101.         OutputStream outputstream = System.out;
  102.         InputReader in = new InputReader(inputstream);
  103.         PrintWriter out = new PrintWriter(outputstream);
  104.         Extract_Primes ep = new Extract_Primes();
  105.         ep.Calculate_primes();
  106.         Perfect_Numbers_Calculation pnc = new Perfect_Numbers_Calculation();
  107.         pnc.Perfect();
  108.         int T;
  109.         T = Integer.parseInt(in.readString());
  110.         for (int i = 1; i <= T; i++) {
  111.             Task solver = new Task();
  112.             solver.solve(i, in, out, ep, pnc);
  113.         }
  114.         out.close();
  115.     }
  116. }
  117.  
  118. class Task {
  119.  
  120.     public void solve(int testno, InputReader in, PrintWriter out, Extract_Primes ep, Perfect_Numbers_Calculation pnc) {
  121.         int N = in.readInt();
  122.         if (N == 1 || N == 2 || N == 3) {
  123.             out.println("1");
  124.         } else if (ep.arr[N] == true) {
  125.             out.println("1");
  126.         } else {
  127.             Number_Of_Positive_Factors nopf = new Number_Of_Positive_Factors();
  128.             int cnt = nopf.Factors(N, ep);
  129.             Fast_Modular_Exponentiation fme = new Fast_Modular_Exponentiation();
  130.             if (pnc.check[N] == false) {
  131.                 int ans = fme.Power(N, (cnt - 2) / 2, 10000);
  132.                 if (ans == 0) {
  133.                     out.println("0000");
  134.                 } else {
  135.                     out.println(ans);
  136.                 }
  137.             } else {
  138.                 int mid = (int) Math.sqrt(N);
  139.                 int ans = fme.Power(mid, (cnt - 2), 10000);
  140.                 if (ans == 0) {
  141.                     out.println("0000");
  142.                 } else {
  143.                     out.println(ans);
  144.                 }
  145.             }
  146.         }
  147.     }
  148. }
  149.  
  150. class InputReader {
  151.  
  152.     private InputStream stream;
  153.     private byte[] buf = new byte[1024];
  154.     private int curChar;
  155.     private int numChars;
  156.  
  157.     public InputReader(InputStream stream) {
  158.         this.stream = stream;
  159.     }
  160.  
  161.     public int read() {
  162.         if (numChars == -1) {
  163.             throw new InputMismatchException();
  164.         }
  165.         if (curChar >= numChars) {
  166.             curChar = 0;
  167.             try {
  168.                 numChars = stream.read(buf);
  169.             } catch (IOException e) {
  170.                 throw new InputMismatchException();
  171.             }
  172.             if (numChars <= 0) {
  173.                 return -1;
  174.             }
  175.         }
  176.         return buf[curChar++];
  177.     }
  178.  
  179.     public int readInt() {
  180.         int c = read();
  181.         while (isSpaceChar(c)) {
  182.             c = read();
  183.         }
  184.         int sgn = 1;
  185.         if (c == '-') {
  186.             sgn = -1;
  187.             c = read();
  188.         }
  189.         int res = 0;
  190.         do {
  191.             if (c < '0' || c > '9') {
  192.                 throw new InputMismatchException();
  193.             }
  194.             res *= 10;
  195.             res += c - '0';
  196.             c = read();
  197.         } while (!isSpaceChar(c));
  198.         return res * sgn;
  199.     }
  200.  
  201.     public String readString() {
  202.         int c = read();
  203.         while (isSpaceChar(c)) {
  204.             c = read();
  205.         }
  206.         StringBuffer res = new StringBuffer();
  207.         do {
  208.             res.appendCodePoint(c);
  209.             c = read();
  210.         } while (!isSpaceChar(c));
  211.         return res.toString();
  212.     }
  213.  
  214.     public long readLong() {
  215.         return Long.parseLong(readString());
  216.     }
  217.  
  218.     public double readDouble() {
  219.         return Double.parseDouble(readString());
  220.     }
  221.  
  222.     public float readFloat() {
  223.         return Float.parseFloat(readString());
  224.     }
  225.  
  226.     public static boolean isSpaceChar(int c) {
  227.         return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  228.     }
  229. }
  230.  
Success #stdin #stdout 0.08s 380224KB
comments (?)
stdin
copy 
6
3
4
12
25
957
10000
stdout
copy 
1
2
144
5
7493
0000
https://ideone.com/kfeqgc
language:
Java (12.0.1)
created:
9 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!