Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- public class Main {
- long mod = 1000*1000*1000+9;
- static long mu(long a, long b, long mod){
- return (a*b)%mod;
- }
- static long bin_pow(long a, long n, long mod){
- if (n == 0) {
- return 1;
- }
- if (n % 2 == 0) {
- long g = bin_pow(a, n/2, mod);
- return mu(g,g, mod);
- } else {
- return mu(a, bin_pow(a,n-1,mod),mod);
- }
- }
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- long mod = 1000*1000*1000+9;
- int n = sc.nextInt();
- long y = mod-2;
- int a[] = new int[n];
- for (int i = 0; i < n; i++){
- a[i] = sc.nextInt();
- }
- for (int i = 0; i <n; i++){
- System.out.println(bin_pow(a[i],y, mod));
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement