QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#574845#9309. Graphgxy001WA 48ms8012kbC++231.2kb2024-09-19 01:37:482024-09-19 01:37:48

Judging History

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

  • [2024-09-19 01:37:48]
  • 评测
  • 测评结果:WA
  • 用时:48ms
  • 内存:8012kb
  • [2024-09-19 01:37:48]
  • 提交

answer

#include<iostream>
#include<cmath>
using std::cin,std::cout;
int const mod=998244353;
int pow(int x,int y){
	int res=1;
	while(y){
		if(y&1) res=1ll*res*x%mod;
		x=1ll*x*x%mod,y>>=1;
	}
	return res;
}
int f0[400010],t,m;
long long n,f1[400010];
auto divide=[](long long N,long long d)->int{return double(N)/d;};
inline long long get(long long x){
	return x<=m?f0[x]:f1[divide(n,x)];
}
int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n;
	m=std::sqrt(n);
	for(int i=1;i<=m;i++){
		f0[i]=i;
		f1[i]=(n/i);
	}
	for(int i=2;i<=m;i++)if(f0[i]!=f0[i-1]){
		int x=f0[i-1];
		long long r=1ll*i*i;
		int u=std::min(1ll*m,n/r),uu=std::min(u,divide(m,i));
		for(int j=1;j<=uu;j++) f1[j]=f1[j]-f1[i*j]+x;
		long long t=n/i;
		for(int j=uu+1;j<=u;j++) f1[j]=f1[j]-f0[divide(t,j)]+x;
		for(int j=m;j>=r;j--) f0[j]=f0[j]-f0[divide(j,i)]+x;
	}
	int ans=1;
	for(long long l=1,r;l<=n;l=r+1){
		r=n/(n/l);
		long long u=n/l;
		if(u==1) break;
		long long k=get(u)-get(u/2);
		int f=1ll*pow(int(u%mod),int(k%(mod-2)))*((u-k-1)%mod)%mod;
		if(u==2) f=1;
		if(u==3) f=3;
		ans=1ll*ans*pow(f,int((r-l+1)%(mod-2)))%mod;
	}
	cout<<ans<<'\n';
	return 0;
}

详细

Test #1:

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

input:

4

output:

8

result:

ok answer is '8'

Test #2:

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

input:

2

output:

1

result:

ok answer is '1'

Test #3:

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

input:

123

output:

671840470

result:

ok answer is '671840470'

Test #4:

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

input:

233

output:

353738465

result:

ok answer is '353738465'

Test #5:

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

input:

5981

output:

970246821

result:

ok answer is '970246821'

Test #6:

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

input:

86422

output:

897815688

result:

ok answer is '897815688'

Test #7:

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

input:

145444

output:

189843901

result:

ok answer is '189843901'

Test #8:

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

input:

901000

output:

819449452

result:

ok answer is '819449452'

Test #9:

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

input:

1000000

output:

113573943

result:

ok answer is '113573943'

Test #10:

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

input:

23333333

output:

949849384

result:

ok answer is '949849384'

Test #11:

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

input:

102850434

output:

604886751

result:

ok answer is '604886751'

Test #12:

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

input:

998244353

output:

0

result:

ok answer is '0'

Test #13:

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

input:

1000000007

output:

318420284

result:

ok answer is '318420284'

Test #14:

score: 0
Accepted
time: 14ms
memory: 8012kb

input:

2147483547

output:

688759898

result:

ok answer is '688759898'

Test #15:

score: 0
Accepted
time: 23ms
memory: 7872kb

input:

5120103302

output:

116870489

result:

ok answer is '116870489'

Test #16:

score: -100
Wrong Answer
time: 48ms
memory: 7184kb

input:

19834593299

output:

572746876

result:

wrong answer expected '523663743', found '572746876'