QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#90370#5062. Squareylf20010818#RE 0ms0kbC++171.2kb2023-03-22 20:17:362023-03-22 20:17:38

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-22 20:17:38]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-03-22 20:17:36]
  • 提交

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

output:


result: