QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#209040#5062. SquareRedDiamondTL 4ms6844kbC++231.4kb2023-10-10 04:52:532023-10-10 04:52:53

Judging History

你现在查看的是最新测评结果

  • [2023-10-10 04:52:53]
  • 评测
  • 测评结果:TL
  • 用时:4ms
  • 内存:6844kb
  • [2023-10-10 04:52:53]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = (int) 1e6 + 5;
const int VAL = (int) 1e6 + 7;
const int M = (int) 1e9 + 7;
int n, a[N];
bool ciur[VAL];

int mul(int a, int b) {
  return a * (ll)b % M;
}

int pw(int a, int b) {
  int r = 1;
  while (b) {
    if (b & 1) r = mul(r, a);
    a = mul(a, a);
    b /= 2;
  }
  return r;
}

signed main() {
#ifdef ONPC
  freopen("input.txt", "r", stdin);
#else
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif // ONPC

  vector<int> primes;
  { /// compute primes
    for (int i = 2; i * i < VAL; i++) {
      if (ciur[i] == 0) {
        for (int j = i * i; j < VAL; j += i) {
          ciur[j] = 1;
        }
      }
    }
    for (int i = 2; i < VAL; i++) {
      if (ciur[i] == 0) {
        primes.push_back(i);
      }
    }
  }

  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }

  int sol = 1;
  for (auto &it : primes) {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
      int e = 0;
      while (a[i] % it == 0) {
        a[i] /= it;
        e++;
      }
      if (e & 1) cnt++;
    }
    int exp = min(cnt, n - cnt);
    sol = mul(sol, pw(it, exp));
  }
  map<int, int> mp;
  for (int i = 1; i <= n; i++) {
    mp[a[i]]++;
  }
  for (auto &it : mp) {
    int exp = min(it.second, n - it.second);
    sol = mul(sol, pw(it.first, exp));
  }
  cout << sol << "\n";
  return 0;
}


詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 6780kb

input:

3
2 3 6

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 4ms
memory: 6844kb

input:

1
1

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: -100
Time Limit Exceeded

input:

100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:


result: