QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#90370 | #5062. Square | ylf20010818# | RE | 0ms | 0kb | C++17 | 1.2kb | 2023-03-22 20:17:36 | 2023-03-22 20:17:38 |
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<ll> prims;
bool vis[M];
ll 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++){
int tt=0;
while(a[i]%x==0) {
a[i]/=x;
tt++;
}
if(tt%2) cnt++;
}
ll mn=min(cnt,n-cnt);
ans=ans*qpow(x,mn)%mod;
}
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<<"\n";
}
详细
Test #1:
score: 0
Runtime Error
input:
3 2 3 6