Submission #50101006

---

Source Code Expand

#include <stdio.h>
#include <stdlib.h>

#define PNUM 333

long long p[PNUM] = {};
long long p_pow[PNUM] = {};

int cmp_ll_PNUM (const void *a, const void *b) {
  long long *a_ = *(long long **)a;
  long long *b_ = *(long long **)b;
  int idx = 0;
  
  while (idx < PNUM) {
    if (a_[idx] < b_[idx]) {
      return -1;
    }
    if (a_[idx] > b_[idx]) {
      return 1;
    }
    idx++;
  }
  
  return 0;
}

int main () {
  int n = 0;
  char a[1001] = "";
  
  int res = 0;
  
  long long ans = 0LL;
  
  long long *a_sort[1000] = {};
  long long a_sort_arr[1000][PNUM] = {};
  long long cnt[1000] = {};
  int ucnt = 0;
  
  p[0] = 2LL;
  for (int i = 1; i < PNUM; i++) {
    int is_ok = 0;
    p[i] = p[i-1]+1LL;
    while (is_ok <= 0) {
      long long tmp = p[i];
      is_ok = 1;
      for (int j = 0; p[j]*p[j] <= p[i]; j++) {
        if (p[i]%p[j] == 0LL) {
          is_ok = 0;
        }
      }
      if (is_ok <= 0) {
        p[i] += 1LL;
      }
    }
  }
  
  for (int i = 0; i < PNUM; i++) {
    p_pow[i] = 1LL;
    while (p_pow[i] <= 2000000000LL/p[i]) {
      p_pow[i] *= p[i];
    }
  }
  
  res = scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    int idx = 0;
    res = scanf("%s", a);
    a_sort[i] = a_sort_arr[i];
    while (a[idx] != '\0') {
      long long d = (long long)(a[idx]-'0');
      idx++;
      for (int j = 0; j < PNUM; j++) {
        a_sort[i][j] *= 10LL;
        a_sort[i][j] += d;
        a_sort[i][j] %= p_pow[j];
      }
    }
  }
  
  qsort(a_sort, n, sizeof(long long *), cmp_ll_PNUM);
  
  cnt[0] = 1LL;
  ucnt = 1;
  for (int i = 1; i < n; i++) {
    if (cmp_ll_PNUM((void *)(a_sort+(i-1)), (void *)(a_sort+i)) != 0) {
      a_sort[ucnt] = a_sort[i];
      ucnt++;
    }
    cnt[ucnt-1] += 1LL;
  }
  
  for (int i = 0; i < ucnt; i++) {
    for (int j = 0; j < i; j++) {
      long long tmp[PNUM] = {};
      long long *tmp_p = tmp;
      int idx[2] = { 0, ucnt };
      int ok[2] = {};
      for (int k = 0; k < PNUM; k++) {
        tmp[k] = (a_sort[j][k]*a_sort[i][k])%p_pow[k];
      }
      while (idx[1]-idx[0] > 1) {
        int nxt = (idx[0]+idx[1])/2;
        int s = ok[0];
        if (s > ok[1]) {
          s = ok[1];
        }
        while (s < PNUM && a_sort[nxt][s] == tmp_p[s]) {
          s++;
        }
        if (s < PNUM && a_sort[nxt][s] > tmp_p[s]) {
          idx[1] = nxt;
          ok[1] = s;
        } else {
          idx[0] = nxt;
          ok[0] = s;
        }
      }
      if (cmp_ll_PNUM((void *)(a_sort+idx[0]), (void *)(&tmp_p)) == 0) {
        ans += cnt[i]*cnt[j]*cnt[idx[0]];
      }
    }
  }
  
  ans <<= 1LL;
  for (int i = 0; i < ucnt; i++) {
    long long tmp[PNUM] = {};
    long long *tmp_p = tmp;
    int idx[2] = { 0, ucnt };
    int ok[2] = {};
    for (int k = 0; k < PNUM; k++) {
      tmp[k] = (a_sort[i][k]*a_sort[i][k])%p_pow[k];
    }
    while (idx[1]-idx[0] > 1) {
      int nxt = (idx[0]+idx[1])/2;
      int s = ok[0];
      if (s > ok[1]) {
        s = ok[1];
      }
      while (s < PNUM && a_sort[nxt][s] == tmp_p[s]) {
        s++;
      }
      if (s < PNUM && a_sort[nxt][s] > tmp_p[s]) {
        idx[1] = nxt;
        ok[1] = s;
      } else {
        idx[0] = nxt;
        ok[0] = s;
      }
    }
    if (cmp_ll_PNUM((void *)(a_sort+idx[0]), (void *)(&tmp_p)) == 0) {
      ans += cnt[i]*cnt[i]*cnt[idx[0]];
    }
  }
  
  printf("%lld\n", ans);
  return 0;
}

Submission Info

Judge Result