QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#211749 | #5062. Square | bigJ | WA | 6ms | 10264kb | C++20 | 3.5kb | 2023-10-12 20:54:14 | 2023-10-12 20:54:15 |
Judging History
answer
#include <bits/stdc++.h>
template<typename P, typename Q> std::istream& operator>>(std::istream& is, std::pair<P, Q>& v) { std::cin >> v.first >> v.second; return is; }
template<typename P, typename Q> std::ostream& operator<<(std::ostream& os, std::pair<P, Q>& v) { std::cout << v.first << ' ' << v.second; return os; }
template<typename T, std::size_t N> std::istream& operator>>(std::istream& is, std::array<T, N>& v) { for (auto& i : v) is >> i; return is; }
template<typename T, std::size_t N> std::ostream& operator<<(std::ostream& os, std::array<T, N>& v) { for (auto& i : v) os << i << ' '; return os; }
template<typename T> std::istream& operator>>(std::istream& is, std::vector<T>& v) { for (auto& i : v) is >> i; return is; }
template<typename T> std::ostream& operator<<(std::ostream& os, std::vector<T>& v) { for (auto& i : v) os << i << ' '; return os; }
template<typename...Args> void debug(Args...args) { ((std::cerr << args << ' '), ...); std::cerr << '\n'; }
template<typename...Args> void println(Args...args) { ((std::cout << args << ' '), ...); std::cout << '\n'; }
template<typename P, typename Q> void chmax(P& a, Q b) { a = (b > a ? b : a); }
template<typename P, typename Q> void chmin(P& a, Q b) { a = (b < a ? b : a); }
using i64 = long long;
std::vector<int> minp, primes;
void sieve(int n) {
minp.assign(n + 1, 0);
primes.clear();
for (int i = 2; i <= n; i++) {
if (minp[i] == 0) {
minp[i] = i;
primes.push_back(i);
}
for (auto p : primes) {
if (i * p > n) {
break;
}
minp[i * p] = p;
if (p == minp[i]) {
break;
}
}
}
}
constexpr int P = 1000000007;
constexpr i64 power(i64 a, i64 b, i64 P = ::P) {
i64 res = 1;
for (; b; b /= 2, a = a * a % P) {
if (b % 2) {
res = res * a % P;
}
}
return res;
}
constexpr i64 inv(i64 a, i64 b = ::P - 2, i64 P = ::P) {
i64 res = 1;
for (; b; b /= 2, a = a * a % P) {
if (b % 2) {
res = res * a % P;
}
}
return res;
}
int main() {
sieve(1000000);
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
int n;
std::cin >> n;
std::vector<int> a(n);
std::cin >> a;
if (n == 1) {
std::cout << "1\n";
return 0;
}
std::vector<std::vector<std::array<int, 2>>> ps(n);
for (int i = 0; i < n; i++) {
int x = a[i];
while (x > 1) {
int p = minp[x];
int t = 0;
while (x % p == 0) {
x /= p;
t++;
}
if (t % 2) {
ps[i].push_back({ p, t });
}
x = minp[x];
}
}
int ans = 1;
for (int i = 0; i < n - 1; i++) {
std::map<int, int> mp;
for (auto [x, t] : ps[i]) {
mp[x] += t;
}
for (auto [x, t] : ps[i + 1]) {
mp[x] += t;
}
for (auto [x, t] : mp) {
if (t % 2) {
ans = 1LL * ans * x % P;
}
}
}
int mn = *std::min_element(a.begin(), a.end());
int cnt = std::count(a.begin(), a.end(), mn);
if (cnt % 2 == 1) {
ans = 1LL * ans * inv(mn) % P;
}
else {
ans = 1LL * ans * mn % P;
}
if (ans < 0) {
ans += P;
}
std::cout << ans << "\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 7732kb
input:
3 2 3 6
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 3ms
memory: 7684kb
input:
1 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 3ms
memory: 10264kb
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:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 3ms
memory: 7600kb
input:
1000 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 1...
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 3ms
memory: 7684kb
input:
1 130321
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 6ms
memory: 7652kb
input:
1 85849
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 3ms
memory: 7456kb
input:
10 1 37249 1 193 1 193 193 193 1 37249
output:
387487994
result:
ok 1 number(s): "387487994"
Test #8:
score: 0
Accepted
time: 3ms
memory: 7728kb
input:
10 130321 130321 6859 6859 6859 19 19 130321 361 6859
output:
130321
result:
ok 1 number(s): "130321"
Test #9:
score: -100
Wrong Answer
time: 6ms
memory: 7588kb
input:
10 1 418609 1 418609 1 1 647 418609 1 1
output:
418609
result:
wrong answer 1st numbers differ - expected: '647', found: '418609'