QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#298282#5062. SquareHJRTL 40ms12584kbC++231.7kb2024-01-05 22:33:302024-01-05 22:33:30

Judging History

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

  • [2024-01-05 22:33:30]
  • 评测
  • 测评结果:TL
  • 用时:40ms
  • 内存:12584kb
  • [2024-01-05 22:33:30]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define debug(x) cout<<#x<<": "<<x<<endl
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll=long long;
using ull=unsigned long long;
#define int long long
const int mo=1000000007;
vector<int> minp, primes;
 
void sieve(int n) {
    minp.assign(n + 1, 0);
    primes.clear();
    
    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }
        
        for (auto p : primes) {
            if (i * p > n) {
                break;
            }
            minp[i * p] = p;
            if (p == minp[i]) {
                break;
            }
        }
    }
}
 
constexpr int V = 1E6;
int ksm(int a,int b,int p)
{
    int res=1;
    while(b)
    {
        if(b&1)
        {
            res=res*a%p;
        }
        a=a*a%p;
        b>>=1;
    }
    return res;
}

void solve(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    ll ans=1;
    map<int,int> cnt;
    for(int i=0;i<n;i++){
        map<int,int> mp;
        int x=a[i];
        for(auto it:primes){
            if(x==1)
                break;
            while(x%it==0){
                x/=it;
                mp[it]++;
            }
        }
        int cur=1;
        for(auto [a1,a2]:mp){
            if(a2%2)
                cnt[a1]++;
        }
    }
    for(auto [a,b]:cnt){
        ans*=ksm(a,min(b,n-b),mo);
        ans%=mo;
    }
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    sieve(V);
    int t=1;
    while(t--){
        solve();
    }
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 11904kb

input:

3
2 3 6

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 9ms
memory: 11912kb

input:

1
1

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 8ms
memory: 12424kb

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: 6ms
memory: 12020kb

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: 9ms
memory: 11932kb

input:

1
130321

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 0ms
memory: 11932kb

input:

1
85849

output:

1

result:

ok 1 number(s): "1"

Test #7:

score: 0
Accepted
time: 3ms
memory: 12000kb

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: 3ms
memory: 11964kb

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: 4ms
memory: 11980kb

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: 6ms
memory: 11924kb

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: 11992kb

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: 15ms
memory: 12540kb

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: 0
Accepted
time: 40ms
memory: 12584kb

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...

output:

716188655

result:

ok 1 number(s): "716188655"

Test #14:

score: -100
Time Limit Exceeded

input:

100000
1 342337 1 342337 342337 342337 342337 1 342337 1 342337 1 342337 1 1 1 1 342337 1 1 1 342337 342337 1 1 342337 342337 1 1 342337 1 1 342337 342337 1 1 342337 342337 1 342337 342337 1 1 1 342337 1 1 1 1 342337 342337 342337 342337 1 342337 1 342337 1 1 1 342337 342337 1 1 1 342337 342337 1 34...

output:


result: