QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#90361 | #5062. Square | ylf20010818# | WA | 92ms | 3768kb | C++17 | 1.2kb | 2023-03-22 19:54:40 | 2023-03-22 19:54:41 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e6+10;
const ll mod=1e9+7;
const int M=1e3;
vector<int> prims;
bool vis[M];
int a[N];
void init(){
for(int i=2;i<=M;i++){
if(vis[i]) continue;
prims.push_back(i);
for(int j=i;j<=M/i;j++) vis[i*j]=1;
}
}
ll qpow(ll x,ll p){
ll res=1;
while(p){
if(p&1) res=res*x%mod;
x=x*x%mod;
p>>=1;
}
return res;
}
map<ll,ll> mp;
int main(){
init();
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
if(n==1){
cout<<1<<"\n";
return 0;
}
ll ans=1;
for(auto x:prims){
int cnt=0;
for(int i=1;i<=n;i++){
if(a[i]%(x*x)&&a[i]%x==0) {
cnt++;
}
while(a[i]%x==0) a[i]/=x;
}
int mn=min(cnt,n-cnt);
// cout<<x<<" "<<mn<<"\n";
ans=ans*qpow(x,mn)%mod;
}
// cout<<ans<<"\n";
for(int i=1;i<=n;i++){
mp[a[i]]++;
}
for(auto x:mp){
ll t1=x.first,t2=x.second;
ll mn=min(n-t2,t2);
ans=ans*qpow(t1,mn)%mod;
}
cout<<ans;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3436kb
input:
3 2 3 6
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
1 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 92ms
memory: 3768kb
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: 3ms
memory: 3348kb
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: 2ms
memory: 3344kb
input:
1 130321
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 2ms
memory: 3344kb
input:
1 85849
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 2ms
memory: 3372kb
input:
10 1 37249 1 193 1 193 193 193 1 37249
output:
387487994
result:
ok 1 number(s): "387487994"
Test #8:
score: -100
Wrong Answer
time: 2ms
memory: 3320kb
input:
10 130321 130321 6859 6859 6859 19 19 130321 361 6859
output:
361
result:
wrong answer 1st numbers differ - expected: '130321', found: '361'