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