QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#567501#9309. GraphchsuhanAC ✓1212ms91476kbC++14925b2024-09-16 12:20:592024-09-16 12:21:00

Judging History

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

  • [2024-09-16 12:21:00]
  • 评测
  • 测评结果:AC
  • 用时:1212ms
  • 内存:91476kb
  • [2024-09-16 12:20:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=10000007,P=998244353;
unordered_map<int,int>mp;
int n,sp[N];
vector<int>p;
int pw(int x,int y){
	int z=1;
	x%=P;
	for(;y>0;y>>=1){
		if(y&1)z=z*x%P;
		x=x*x%P;
	}
	return z;
}
int sp_(int x){
	if(x<N)return sp[x];
	return mp[x];
}
void getsp(){
	for(int i=1;p[i]*p[i]<=n;i++)
		for(int j=n;j>=p[i]*p[i];j=n/(n/j+1))
			(j<N?sp[j]:mp[j])-=sp_(j/p[i])-sp[p[i-1]];
}
int f(int x){
	if(x<=3)return pw(x,x-2);
	int m=sp_(x)-sp_(x/2)+2;
	return (x-m+1)%P*pw(x,m-2)%P;
}
signed main(){
	cin>>n;
	p.push_back(1);
	for(int i=2;i<N;i++){
		if(sp[i])continue;
		p.push_back(i);
		for(int j=i*i;j<N;j+=i)sp[j]=1;
	}
	for(int i=n;i>1;i=n/(n/i+1)){
		if(i<N)sp[i]=i-1;
		else mp[i]=i-1;
	}
	getsp();
	int ans=1;
	for(int l=1,r;l<=n;l=r+1){
		r=n/(n/l);
		ans=ans*pw(f(n/l),r-l+1)%P;
	}
	cout<<ans;
	return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 150ms
memory: 90152kb

input:

4

output:

8

result:

ok answer is '8'

Test #2:

score: 0
Accepted
time: 151ms
memory: 90220kb

input:

2

output:

1

result:

ok answer is '1'

Test #3:

score: 0
Accepted
time: 156ms
memory: 90200kb

input:

123

output:

671840470

result:

ok answer is '671840470'

Test #4:

score: 0
Accepted
time: 157ms
memory: 90208kb

input:

233

output:

353738465

result:

ok answer is '353738465'

Test #5:

score: 0
Accepted
time: 151ms
memory: 89864kb

input:

5981

output:

970246821

result:

ok answer is '970246821'

Test #6:

score: 0
Accepted
time: 154ms
memory: 91476kb

input:

86422

output:

897815688

result:

ok answer is '897815688'

Test #7:

score: 0
Accepted
time: 139ms
memory: 91264kb

input:

145444

output:

189843901

result:

ok answer is '189843901'

Test #8:

score: 0
Accepted
time: 148ms
memory: 90736kb

input:

901000

output:

819449452

result:

ok answer is '819449452'

Test #9:

score: 0
Accepted
time: 157ms
memory: 90388kb

input:

1000000

output:

113573943

result:

ok answer is '113573943'

Test #10:

score: 0
Accepted
time: 153ms
memory: 90044kb

input:

23333333

output:

949849384

result:

ok answer is '949849384'

Test #11:

score: 0
Accepted
time: 154ms
memory: 90924kb

input:

102850434

output:

604886751

result:

ok answer is '604886751'

Test #12:

score: 0
Accepted
time: 185ms
memory: 90620kb

input:

998244353

output:

0

result:

ok answer is '0'

Test #13:

score: 0
Accepted
time: 202ms
memory: 90364kb

input:

1000000007

output:

318420284

result:

ok answer is '318420284'

Test #14:

score: 0
Accepted
time: 213ms
memory: 90888kb

input:

2147483547

output:

688759898

result:

ok answer is '688759898'

Test #15:

score: 0
Accepted
time: 278ms
memory: 90568kb

input:

5120103302

output:

116870489

result:

ok answer is '116870489'

Test #16:

score: 0
Accepted
time: 473ms
memory: 90164kb

input:

19834593299

output:

523663743

result:

ok answer is '523663743'

Test #17:

score: 0
Accepted
time: 794ms
memory: 90720kb

input:

52500109238

output:

195086665

result:

ok answer is '195086665'

Test #18:

score: 0
Accepted
time: 1069ms
memory: 89804kb

input:

84848352911

output:

107959260

result:

ok answer is '107959260'

Test #19:

score: 0
Accepted
time: 1205ms
memory: 89784kb

input:

99824435322

output:

0

result:

ok answer is '0'

Test #20:

score: 0
Accepted
time: 1212ms
memory: 91328kb

input:

99999999354

output:

316301711

result:

ok answer is '316301711'

Test #21:

score: 0
Accepted
time: 1204ms
memory: 89660kb

input:

100000000000

output:

396843576

result:

ok answer is '396843576'

Extra Test:

score: 0
Extra Test Passed