QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#450537 | #5062. Square | zzzwsnd | TL | 720ms | 4376kb | C++14 | 887b | 2024-06-22 15:16:52 | 2024-06-22 15:16:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const long long mod= 1000000007;
int a[110000];
bool b[1100000];
int c[100000];
int d[100000];
long long mi(long long x,long long y){
long long base=1;
while(y)
{
if(y&1) base=base*x%mod;
y>>=1;
x=x*x%mod;
}
return base;
}
int main(){
int n,ma=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
ma=max(ma,a[i]);
}
int l=0;
for(int i=2;i<=ma;i++){
while(b[i])i++;
if(i>ma)
break;
c[++l]=i;
// cout<<i<<endl;
for(int j=i;j<=ma;j+=i){
b[j]=1;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=l;j++){
int fl=0;
while(a[i]%c[j]==0){
fl++;
a[i]=a[i]/c[j];
}
d[j]+=(fl%2);
}
}
long long sum=1;
for(int i=1;i<=l;i++){
sum=(sum*mi((long long)c[i],min((long long)d[i],(long long)n-(long long)d[i])));
sum=sum%mod;
}
cout<<sum<<endl;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3648kb
input:
3 2 3 6
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
1 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 9ms
memory: 4032kb
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: 0ms
memory: 3652kb
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: 1ms
memory: 3932kb
input:
1 130321
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
1 85849
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3600kb
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: 1ms
memory: 3880kb
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: 3ms
memory: 4336kb
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: 1ms
memory: 3860kb
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: 4376kb
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: 720ms
memory: 4112kb
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: -100
Time Limit Exceeded
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...