QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#298282 | #5062. Square | HJR | TL | 40ms | 12584kb | C++23 | 1.7kb | 2024-01-05 22:33:30 | 2024-01-05 22:33:30 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define debug(x) cout<<#x<<": "<<x<<endl
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll=long long;
using ull=unsigned long long;
#define int long long
const int mo=1000000007;
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 V = 1E6;
int ksm(int a,int b,int p)
{
int res=1;
while(b)
{
if(b&1)
{
res=res*a%p;
}
a=a*a%p;
b>>=1;
}
return res;
}
void solve(){
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++)
cin>>a[i];
ll ans=1;
map<int,int> cnt;
for(int i=0;i<n;i++){
map<int,int> mp;
int x=a[i];
for(auto it:primes){
if(x==1)
break;
while(x%it==0){
x/=it;
mp[it]++;
}
}
int cur=1;
for(auto [a1,a2]:mp){
if(a2%2)
cnt[a1]++;
}
}
for(auto [a,b]:cnt){
ans*=ksm(a,min(b,n-b),mo);
ans%=mo;
}
cout<<ans;
}
signed main(){
ios::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
sieve(V);
int t=1;
while(t--){
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 11904kb
input:
3 2 3 6
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 9ms
memory: 11912kb
input:
1 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 8ms
memory: 12424kb
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: 12020kb
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: 9ms
memory: 11932kb
input:
1 130321
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 11932kb
input:
1 85849
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 3ms
memory: 12000kb
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: 11964kb
input:
10 130321 130321 6859 6859 6859 19 19 130321 361 6859
output:
130321
result:
ok 1 number(s): "130321"
Test #9:
score: 0
Accepted
time: 4ms
memory: 11980kb
input:
10 1 418609 1 418609 1 1 647 418609 1 1
output:
647
result:
ok 1 number(s): "647"
Test #10:
score: 0
Accepted
time: 6ms
memory: 11924kb
input:
10 85849 293 1 293 1 1 85849 293 293 293
output:
424869580
result:
ok 1 number(s): "424869580"
Test #11:
score: 0
Accepted
time: 3ms
memory: 11992kb
input:
10 16384 2048 8192 512 65536 524288 65536 4 2 262144
output:
32
result:
ok 1 number(s): "32"
Test #12:
score: 0
Accepted
time: 15ms
memory: 12540kb
input:
100000 1 197 1 38809 197 197 38809 1 197 197 1 38809 38809 1 1 1 1 38809 197 1 1 1 1 38809 197 197 1 38809 1 1 38809 38809 1 197 1 197 38809 38809 197 197 38809 1 38809 38809 197 38809 38809 197 197 1 38809 38809 38809 38809 38809 197 38809 38809 197 1 1 197 38809 38809 38809 197 1 1 1 197 197 197 1...
output:
810775411
result:
ok 1 number(s): "810775411"
Test #13:
score: 0
Accepted
time: 40ms
memory: 12584kb
input:
100000 1 1 597529 773 1 597529 1 773 1 597529 773 773 597529 773 597529 1 597529 773 773 1 1 597529 597529 773 773 597529 1 597529 1 1 773 773 1 597529 597529 597529 597529 597529 597529 773 597529 773 1 773 597529 773 1 1 773 773 773 597529 597529 1 1 773 773 773 773 597529 597529 597529 773 773 77...
output:
716188655
result:
ok 1 number(s): "716188655"
Test #14:
score: -100
Time Limit Exceeded
input:
100000 1 342337 1 342337 342337 342337 342337 1 342337 1 342337 1 342337 1 1 1 1 342337 1 1 1 342337 342337 1 1 342337 342337 1 1 342337 1 1 342337 342337 1 1 342337 342337 1 342337 342337 1 1 1 342337 1 1 1 1 342337 342337 342337 342337 1 342337 1 342337 1 1 1 342337 342337 1 1 1 342337 342337 1 34...