QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#211740#5062. SquarebigJWA 6ms10312kbC++203.2kb2023-10-12 20:48:422023-10-12 20:48:43

Judging History

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

  • [2023-10-12 20:48:43]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:10312kb
  • [2023-10-12 20:48:42]
  • 提交

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 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 mn = 1e9 + 8;

    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 == 1) {
                ans = 1LL * ans * x % P;
                chmin(mn, x);
            }
        }
    }

    ans = 1LL * ans * inv(mn) % P;
    if (ans < 0) {
        ans += P;
    }
    

    std::cout << ans << "\n";

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 6ms
memory: 7468kb

input:

3
2 3 6

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 6ms
memory: 7424kb

input:

1
1

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 3ms
memory: 10312kb

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: 6ms
memory: 7688kb

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: 7636kb

input:

1
130321

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 3ms
memory: 7748kb

input:

1
85849

output:

1

result:

ok 1 number(s): "1"

Test #7:

score: -100
Wrong Answer
time: 3ms
memory: 7732kb

input:

10
1 37249 1 193 1 193 193 193 1 37249

output:

7189057

result:

wrong answer 1st numbers differ - expected: '387487994', found: '7189057'