QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#90371#5062. Squareylf20010818#AC ✓98ms5176kbC++171.3kb2023-03-22 20:19:322023-03-22 20:19:35

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:19:35]
  • 评测
  • 测评结果:AC
  • 用时:98ms
  • 内存:5176kb
  • [2023-03-22 20:19: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];
    }
    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++;
        }
        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: 3344kb

input:

3
2 3 6

output:

6

result:

ok 1 number(s): "6"

Test #2:

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

input:

1
1

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 82ms
memory: 3724kb

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

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

input:

1
130321

output:

1

result:

ok 1 number(s): "1"

Test #6:

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

input:

1
85849

output:

1

result:

ok 1 number(s): "1"

Test #7:

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

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: 2ms
memory: 3500kb

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: 2ms
memory: 3480kb

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

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

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: 58ms
memory: 3732kb

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: 61ms
memory: 3868kb

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: 0
Accepted
time: 62ms
memory: 3600kb

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:

158685643

result:

ok 1 number(s): "158685643"

Test #15:

score: 0
Accepted
time: 62ms
memory: 3600kb

input:

100000
877 1 1 877 877 877 1 769129 877 769129 769129 877 877 769129 877 769129 877 769129 877 1 769129 877 877 1 769129 877 769129 877 769129 1 769129 769129 877 877 769129 877 877 769129 877 877 1 877 769129 1 877 1 1 769129 769129 769129 1 1 877 769129 1 1 1 1 769129 877 877 769129 769129 877 1 1...

output:

208442677

result:

ok 1 number(s): "208442677"

Test #16:

score: 0
Accepted
time: 62ms
memory: 3720kb

input:

100000
347 1 120409 120409 120409 347 347 347 120409 1 347 1 1 347 120409 1 1 120409 1 347 1 1 1 347 120409 347 1 1 120409 120409 1 1 1 347 1 1 120409 120409 120409 347 120409 347 120409 347 347 347 1 347 1 1 1 347 347 1 120409 1 1 1 347 1 347 347 120409 120409 1 120409 120409 120409 347 1 120409 1 ...

output:

177423905

result:

ok 1 number(s): "177423905"

Test #17:

score: 0
Accepted
time: 63ms
memory: 3732kb

input:

100000
1 961 961 961 1 961 961 31 1 31 29791 31 1 31 29791 923521 1 31 961 29791 923521 961 1 923521 923521 923521 923521 923521 923521 923521 1 923521 1 29791 923521 29791 1 923521 29791 961 923521 1 961 923521 31 31 961 29791 923521 31 923521 31 923521 961 31 961 923521 961 961 923521 923521 92352...

output:

524153120

result:

ok 1 number(s): "524153120"

Test #18:

score: 0
Accepted
time: 67ms
memory: 3892kb

input:

100000
1 1 844561 844561 1 844561 1 919 844561 919 1 844561 919 1 1 844561 1 919 919 1 919 844561 919 1 919 919 919 844561 844561 919 919 1 919 919 919 1 919 1 844561 1 919 919 844561 919 844561 844561 844561 844561 919 1 844561 844561 1 1 844561 1 919 844561 844561 844561 1 919 844561 844561 919 91...

output:

626715414

result:

ok 1 number(s): "626715414"

Test #19:

score: 0
Accepted
time: 63ms
memory: 3728kb

input:

100000
159097 1 159097 159097 1 159097 159097 1 1 1 159097 1 159097 159097 159097 1 159097 1 1 1 159097 1 1 159097 1 159097 159097 1 1 159097 159097 1 159097 159097 1 1 1 1 1 1 1 159097 159097 159097 159097 1 1 1 1 159097 159097 159097 159097 1 159097 159097 1 159097 1 1 1 1 159097 159097 1 159097 1...

output:

25918992

result:

ok 1 number(s): "25918992"

Test #20:

score: 0
Accepted
time: 63ms
memory: 3712kb

input:

100000
521 521 271441 1 271441 1 271441 1 1 521 1 521 1 1 1 521 271441 271441 1 271441 1 271441 1 271441 521 271441 1 1 521 271441 521 271441 521 1 271441 271441 271441 1 271441 271441 271441 521 521 271441 1 521 521 271441 521 521 271441 521 271441 271441 1 521 271441 521 521 521 1 271441 271441 1 ...

output:

713140981

result:

ok 1 number(s): "713140981"

Test #21:

score: 0
Accepted
time: 76ms
memory: 3824kb

input:

100000
256 16 16384 524288 131072 4 16384 4096 4 4096 8192 65536 32 1024 2 8 4 2048 4096 8 65536 512 1024 4 256 16384 256 131072 2 4096 2 2 4096 32768 524288 2048 16 131072 8192 32768 1 2 128 262144 16 32768 131072 2048 32768 8192 262144 32768 1024 262144 131072 4096 128 16 32768 1024 32 32768 16384...

output:

477168076

result:

ok 1 number(s): "477168076"

Test #22:

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

input:

1
136045

output:

1

result:

ok 1 number(s): "1"

Test #23:

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

input:

10
796938 169406 128933 247568 498433 734706 88188 32093 71322 347806

output:

240205168

result:

ok 1 number(s): "240205168"

Test #24:

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

input:

100
906441 591513 587396 725800 289176 795472 285873 252939 267359 68981 135395 870454 845379 405859 10575 503075 150322 234161 7065 507984 198629 399148 516285 761467 978641 44092 475210 984670 593559 372611 157148 10541 152581 975840 481026 250318 658614 251540 137765 66821 155356 723708 397316 21...

output:

320217691

result:

ok 1 number(s): "320217691"

Test #25:

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

input:

1000
145908 709080 951048 574849 433852 58975 996317 632258 249598 674305 961946 396206 846505 498154 937245 933404 295141 226365 248878 687472 411883 873979 882346 34661 289173 90931 785823 34858 477465 975859 852767 273949 494367 748789 576526 88147 230621 256598 262366 503179 475295 877199 775934...

output:

942871229

result:

ok 1 number(s): "942871229"

Test #26:

score: 0
Accepted
time: 11ms
memory: 3672kb

input:

10000
776461 370678 155936 667113 314224 537923 53654 516617 447466 667774 724242 262599 413001 449878 299751 793335 636264 502558 420963 216383 45836 422004 708237 991951 784208 806216 667401 671788 797472 793770 779019 641955 415579 25581 156836 928974 978938 579615 860359 514240 745294 698112 987...

output:

477526680

result:

ok 1 number(s): "477526680"

Test #27:

score: 0
Accepted
time: 78ms
memory: 5044kb

input:

100000
64506 894411 909371 316716 69916 633903 244728 606909 718902 282485 928029 600089 756607 464736 192047 407397 786130 329452 104363 229690 835836 923293 776289 106301 521843 314656 496214 29483 888963 59387 549223 307524 386886 159601 927058 527693 933151 833635 100341 208027 413118 426597 586...

output:

639576060

result:

ok 1 number(s): "639576060"

Test #28:

score: 0
Accepted
time: 84ms
memory: 5176kb

input:

100000
915010 50743 110014 154804 645423 485880 399919 930157 90428 848957 99477 662553 887850 722970 261256 760614 214010 788124 783981 53496 530856 259992 762316 13465 45404 39175 462032 177278 309568 410660 288940 543390 840737 244001 894258 250545 229382 858072 710348 255668 109160 225440 82001 ...

output:

763800461

result:

ok 1 number(s): "763800461"

Test #29:

score: 0
Accepted
time: 80ms
memory: 5044kb

input:

100000
67181 964140 121873 355240 628862 154671 193527 184567 2172 962789 898978 525672 372690 647857 695067 594245 176179 762985 164259 799237 71180 799605 246710 307365 152344 91576 697076 425692 764400 539573 222282 886847 620814 734725 593970 980618 277489 24687 616749 457802 247968 107049 88599...

output:

610083858

result:

ok 1 number(s): "610083858"

Test #30:

score: 0
Accepted
time: 81ms
memory: 5028kb

input:

100000
611562 708316 855418 834189 689766 250358 698000 783150 747944 187987 560134 879194 628658 508629 479744 812309 63423 89118 872018 241257 788861 149091 845961 173117 390961 5509 288904 443513 806838 267572 394157 981852 419766 909674 265729 885724 947330 770251 292417 748538 324650 453688 960...

output:

683032414

result:

ok 1 number(s): "683032414"

Test #31:

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

input:

1
36465

output:

1

result:

ok 1 number(s): "1"

Test #32:

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

input:

10
72930 3570 51 3003 1155 255 102102 1309 22 34034

output:

836099040

result:

ok 1 number(s): "836099040"

Test #33:

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

input:

100
390 385 102102 143 55 2002 715 1155 273 182 14 130 17 12155 663 26 7293 1 39270 231 273 30 255 91 7 1190 2 3 910 286 3927 70 1155 715 30030 715 195 7 255 1190 102 714 21 17 55 6630 17 170 429 170 7854 910 170 2 34 70 2805 1870 1 7854 1001 1870 21 858 55 2618 429 91 935 10010 357 286 17 1326 462 ...

output:

416023308

result:

ok 1 number(s): "416023308"

Test #34:

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

input:

1000
3 10 36465 154 85085 4862 39270 15 78 2431 14 4862 102 119 4641 4641 6006 2002 110 7854 2145 595 195 154 561 6006 7 255 429 510510 15015 119 442 70 70 3570 15470 462 14586 286 510510 3003 510510 24310 17017 15 6 7854 210 15015 462 170 7 165 4641 3315 3 187 2805 714 154 2730 546 2002 6545 210 39...

output:

443329488

result:

ok 1 number(s): "443329488"

Test #35:

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

input:

10000
65 1870 6630 2002 7 51051 7 7 102 66 2310 33 1155 91 6630 22 770 170170 19635 130 273 6006 2730 102 7 3315 30030 102 70 170170 2210 13090 33 2310 14 2210 7 165 170170 6545 102102 2805 19635 2 12155 195 455 24310 357 715 4290 10010 935 30030 105 1430 3570 1547 1155 39 357 9282 10010 255 255 100...

output:

949683104

result:

ok 1 number(s): "949683104"

Test #36:

score: 0
Accepted
time: 67ms
memory: 3596kb

input:

100000
23205 26 714 102102 182 165 273 7735 91 24310 273 286 1001 24310 221 14586 561 3094 357 5 357 3315 2618 2 110 561 36465 105 1309 1190 119 13 130 1785 770 3315 2730 165 330 357 15 119 9282 6 255255 65 1870 105 34034 561 130 6006 5610 17 595 273 24310 3927 455 15470 19635 7 3 6545 170 46410 546...

output:

861561962

result:

ok 1 number(s): "861561962"

Test #37:

score: 0
Accepted
time: 93ms
memory: 3888kb

input:

100000
14586 46410 462 5 6630 2145 154 330 7735 455 4641 2 7735 65 10010 1326 462 4290 3927 12155 2145 34034 1870 770 4641 33 22 39270 10 102102 442 51051 15 42 42 51 1870 1326 35 2145 231 51 85085 11 273 130 26 1 1105 6630 3003 21 5005 286 2002 154 455 91 255255 210 510510 119 102102 21 14586 1155 ...

output:

441968208

result:

ok 1 number(s): "441968208"

Test #38:

score: 0
Accepted
time: 98ms
memory: 3608kb

input:

100000
2145 1326 119 510 1326 5005 385 19635 561 36465 46410 273 273 3003 39 910 7735 255255 1365 3003 2145 5 1785 65 15015 231 170170 42 374 15015 1430 102102 4290 9282 2310 34 19635 770 22 273 2210 1105 510 210 15 3927 330 55 273 7854 85085 12155 30030 7735 91 374 102 46410 4641 46410 46410 231 23...

output:

976796051

result:

ok 1 number(s): "976796051"

Test #39:

score: 0
Accepted
time: 72ms
memory: 3728kb

input:

100000
102102 72930 5005 1122 51 5 26 330 5 17 6545 39270 6630 510510 17017 36465 1309 154 510 231 255 19635 143 273 2618 26 102 1001 14 510510 77 429 6630 330 130 210 19635 119 39270 33 39270 286 561 165 561 143 1105 66 21 154 4290 1785 51051 3315 2730 1547 935 5 286 390 21 714 221 77 231 238 2002 ...

output:

997010956

result:

ok 1 number(s): "997010956"