QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#450540#5062. SquarezzzwsndTL 25ms5872kbC++14966b2024-06-22 15:20:262024-06-22 15:20:26

Judging History

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

  • [2024-06-22 15:20:26]
  • 评测
  • 测评结果:TL
  • 用时:25ms
  • 内存:5872kb
  • [2024-06-22 15:20:26]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const long long mod= 1000000007;
int a[110000];
bool b[1100000];
int c[100000];
int d[100000];
long long mi(long long x,long long y){
	long long base=1;
	while(y)
	{
		if(y&1) base=base*x%mod;
		y>>=1;
		x=x*x%mod;
	}
	return base;
}
int main(){
	ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
	int n,ma=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ma=max(ma,a[i]);
	}
	int l=0;
	for(int i=2;i<=ma;i++){
		while(b[i])i++;
		if(i>ma)
		break;
		c[++l]=i;
	//	cout<<i<<endl;
		for(int j=i;j<=ma;j+=i){
			b[j]=1;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=l;j++){
			int fl=0;
			if(a[i]==1)
			break;
			while(a[i]%c[j]==0){
				fl++;
				a[i]=a[i]/c[j];
			}
			d[j]+=(fl%2);
		} 
	} 
	long long sum=1; 
	for(int i=1;i<=l;i++){
		sum=(sum*mi((long long)c[i],min((long long)d[i],(long long)n-(long long)d[i])));
		sum=sum%mod;
		
	}
	cout<<sum;
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5708kb

input:

3
2 3 6

output:

6

result:

ok 1 number(s): "6"

Test #2:

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

input:

1
1

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

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

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

input:

1
130321

output:

1

result:

ok 1 number(s): "1"

Test #6:

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

input:

1
85849

output:

1

result:

ok 1 number(s): "1"

Test #7:

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

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

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

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

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

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: 11ms
memory: 5872kb

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: 25ms
memory: 5700kb

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: