fork(1) download
copy 
  1.  
  2.        #include<bits/stdc++.h>
  3.  
  4.      #define MAX 500000
  5.  
  6.  
  7.  
  8.     int Power(int b, int p, int mod) {
  9.  
  10.         long long ans=1,y=b;
  11.         while (p > 0) {
  12.             if ((p & 1) == 1) {
  13.                 ans = (ans * y) % mod;
  14.             }
  15.             y = (y * y) % mod;
  16.             p >>= 1;
  17.         }
  18.         return (int)(ans % mod);
  19.     }
  20.  
  21.  
  22.  
  23.  
  24.  
  25.      bool arr[MAX+1];
  26.     int LIMIT = (int)sqrt(MAX);
  27.     int primes[MAX];
  28.     int sz = 0;
  29.  
  30.      void E_primes() {
  31.         for (int i = 2; i <= MAX; i++) {
  32.             if (arr[i] == true) {
  33.                 primes[sz++] = i;
  34.             }
  35.         }
  36.     }
  37.  
  38.      void Calculate_primes() {
  39.  
  40.         for (int i = 0; i <= MAX; i++) {
  41.             arr[i] = true;
  42.         }
  43.         arr[0] = arr[1] = false;
  44.         for (int i = 2; i <= LIMIT;) {
  45.             if (arr[i] == true) {
  46.                 for (int j = i + i; j <= MAX; j += i) {
  47.                     arr[j] = false;
  48.                 }
  49.             }
  50.             if (i == 2) {
  51.                 i += 1;
  52.             } else {
  53.                 i += 2;
  54.             }
  55.         }
  56.         E_primes();
  57.     }
  58.  
  59.  
  60.  
  61.  
  62.  
  63.     int Factors(int no) {
  64.  
  65.          int cnt = 1;
  66.           int ans = 1;
  67.  
  68.         int number = no;
  69.         for (int i = 0; i < sz && (primes[i] <= (int)sqrt(number)); i++) {
  70.             cnt = 1;
  71.             while (number % primes[i] == 0) {
  72.                 cnt++;
  73.                 number /= primes[i];
  74.             }
  75.             ans *= cnt;
  76.         }
  77.         if (number > 1) {
  78.             ans = ans * 2;
  79.         }
  80.         return (ans);
  81.     }
  82.  
  83.  
  84.  
  85.        bool check[MAX+1];
  86.  
  87.      void Perfect() {
  88.  
  89.         check[0] = false;
  90.         for (int i = 1; i * i <= MAX; i++) {
  91.             check[i * i] = true;
  92.         }
  93.     }
  94.  
  95.  
  96.  
  97.  
  98.        int main(void){
  99.  
  100.        int T;
  101.        Calculate_primes();
  102.        Perfect();
  103.        scanf("%d",&T);
  104.        while(T--){
  105.         int N;
  106.         scanf("%d",&N);
  107.         if(N==1||N==2||N==3)
  108.             printf("1\n");
  109.         else if (arr[N]==true)
  110.             printf("1\n");
  111.              else {
  112.             int cnt = Factors(N);
  113.             if (check[N] == false) {
  114.                 int ans = Power(N, (cnt - 2) / 2, 10000);
  115.                 if (ans == 0) {
  116.                     printf("0000\n");
  117.                 } else {
  118.                     printf("%d\n",ans);
  119.                 }
  120.             } else {
  121.                 int mid = (int)sqrt(N);
  122.                 int ans = Power(mid, (cnt - 2), 10000);
  123.                 if (ans == 0) {
  124.                     printf("0000\n");
  125.                 } else {
  126.                     printf("%d\n",ans);
  127.                 }
  128.             }
  129.         }
  130.        }
  131.        }
  132.  
Success #stdin #stdout 0s 6272KB
comments (?)
stdin
copy 
6
3
4
12
25
957
10000
stdout
copy 
1
2
144
5
7493
0000
https://ideone.com/rHBBrW
language:
C++14 (gcc 8.3)
created:
11 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!