QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#301785 | #5062. Square | ginkgozyf# | RE | 24ms | 11388kb | C++20 | 1.7kb | 2024-01-10 11:32:17 | 2024-01-10 11:32:17 |
Judging History
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;
}
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
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: 24ms
memory: 11388kb
input:
3 2 3 6
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: -100
Runtime Error
input:
1 1