QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#90356#5062. Squareylf20010818#WA 96ms3820kbC++171.2kb2023-03-22 19:40:322023-03-22 19:40:34

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 19:40:34]
  • 评测
  • 测评结果:WA
  • 用时:96ms
  • 内存:3820kb
  • [2023-03-22 19:40:32]
  • 提交

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];
    }
    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: 3372kb

input:

3
2 3 6

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3324kb

input:

1
1

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 96ms
memory: 3820kb

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: 1ms
memory: 3320kb

input:

1
130321

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 2ms
memory: 3340kb

input:

1
85849

output:

1

result:

ok 1 number(s): "1"

Test #7:

score: 0
Accepted
time: 2ms
memory: 3344kb

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: 0ms
memory: 3216kb

input:

10
130321 130321 6859 6859 6859 19 19 130321 361 6859

output:

361

result:

wrong answer 1st numbers differ - expected: '130321', found: '361'