QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#301783#5062. Squareginkgozyf#RE 28ms11348kbC++201.6kb2024-01-10 11:27:532024-01-10 11:27:53

Judging History

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

  • [2024-01-10 11:27:53]
  • 评测
  • 测评结果:RE
  • 用时:28ms
  • 内存:11348kb
  • [2024-01-10 11:27:53]
  • 提交

answer

#include<bits/stdc++.h>
#define endl "\n"
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 50, M = 1e6 + 50, inf = 0x3f3f3f3f, P = 13331, mod = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, a[N], b[N];
int f[M];
void init(){
    for(int i=2;i<M;i++){
        for(int j=i;j<M;j+=i){
            if(f[j]) continue;
            else f[j]=i;
        }
    }
}
int shai(int a, int b = 1, int c = 1) {
    int res=1;
    map<int, int> cnt;
    while(f[a]){
        cnt[f[a]]++;
        a/=f[a];
    }
    while(f[b]){
        cnt[f[b]]++;
        b/=f[b];
    }
    while (f[c]) {
        cnt[f[c]]++;
        c /= f[c];
    }
    for (auto [u, v] : cnt) {
        if (v & 1) res *= u;
    }
    return res;
}

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

    if(n == 1) {
        cout << shai(a[1]) << endl;
    } else if(n == 2) {
        cout << shai(a[1], a[2]) % mod << endl;
    }

    int t1 = a[1] * a[2], t2 = a[2] * a[3];
    int tmp = gcd(t1, t2);
    tmp /= gcd(a[2], tmp);
    b[2] = tmp;

    b[1] = shai(a[1],a[2],b[2]);

    for(int i = 3; i <= n; i ++ ) {
        b[i] = shai(a[i - 1],a[i],b[i - 1]);
    }

    int res = 1;

    for(int i = 1; i <= n; i ++ ) {
        (res *= b[i]) %= mod;
    }

    cout << res << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    init();
    for(int i = 1; i <= t; i ++ ) {
        solve();
    }

}

详细

Test #1:

score: 100
Accepted
time: 28ms
memory: 11348kb

input:

3
2 3 6

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: -100
Runtime Error

input:

1
1

output:


result: