QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#620338#9309. Graphsz051WA 273ms10460kbC++201.7kb2024-10-07 17:35:182024-10-07 17:35:19

Judging History

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

  • [2024-10-07 17:35:19]
  • 评测
  • 测评结果:WA
  • 用时:273ms
  • 内存:10460kb
  • [2024-10-07 17:35:18]
  • 提交

answer

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#define int long long
using namespace std;

const int md=998244353,B=320000;
void read(int &x){
	x=0;
	int f=1;
	char c=getchar();
	while(!('0'<=c && c<='9')){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while('0'<=c && c<='9'){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	x*=f;
}
int powr(int b,int k){
	b%=md;
	int res=1;
	for(;k;k>>=1,b=b*b%md){
		if(k&1){
			res=res*b%md;
		}
	}
	return res;
}
int ps[100010],cnt=0;
bool isp[1000010];
void sieve(int n){
	memset(isp,1,sizeof(isp));
	isp[0]=isp[1]=0;
	for(int i=2;i<=n;i++){
		if(isp[i]){
			ps[++cnt]=i;
		}
		for(int j=1;j<=cnt && ps[j]*i<=n;j++){
			isp[ps[j]*i]=0;
			if(i%ps[j]==0){
				break;
			}
		}
	}
}
int n,sum1[1000010],sum2[1000010];
int getres(int k){
	if(n/k<=2){
		return 1;
	}else if(n/k==3){
		return 3;
	}else{
		int cur=((n/k<=B?sum1[n/k]:sum2[k])-(n/(2*k)<=B?sum1[n/(2*k)]:sum2[2*k]))%md;
		return (n/k-cur-1)%md*powr(n/k,cur)%md; 
	}
}
signed main(){
	sieve(B);
	read(n);
	for(int i=1;i<=min(B,n);i++){
		sum1[i]=i-1;
	}
	for(int i=1;i<=B;i++){
		if(n/i<=B){
			break;
		}
		sum2[i]=n/i-1;
	}
	for(int j=1;j<=cnt;j++){
		int p=ps[j];
		if(p*p>n){
			break;
		}
		for(int i=1;i<=B;i++){
			if(n/i<=B){
				break;
			}
			int v=n/i;
			if(p*p>v){
				break;
			}
			sum2[i]-=(v/p<=B?sum1[v/p]:sum2[i*p])-j+1;
		}
		for(int i=B;i;i--){
			if(p*p>i){
				break;
			}
			sum1[i]-=sum1[i/p]-j+1;
		}
	}
	int res=1;
	for(int l=1,r;l<=n;l=r+1){
		r=n/(n/l);
		res=res*powr(getres(l),r-l+1)%md;
	}
	printf("%lld",res);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 7628kb

input:

4

output:

8

result:

ok answer is '8'

Test #2:

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

input:

2

output:

1

result:

ok answer is '1'

Test #3:

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

input:

123

output:

671840470

result:

ok answer is '671840470'

Test #4:

score: 0
Accepted
time: 4ms
memory: 7200kb

input:

233

output:

353738465

result:

ok answer is '353738465'

Test #5:

score: 0
Accepted
time: 22ms
memory: 6760kb

input:

5981

output:

970246821

result:

ok answer is '970246821'

Test #6:

score: 0
Accepted
time: 51ms
memory: 10072kb

input:

86422

output:

897815688

result:

ok answer is '897815688'

Test #7:

score: 0
Accepted
time: 59ms
memory: 7824kb

input:

145444

output:

189843901

result:

ok answer is '189843901'

Test #8:

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

input:

901000

output:

819449452

result:

ok answer is '819449452'

Test #9:

score: 0
Accepted
time: 71ms
memory: 7664kb

input:

1000000

output:

113573943

result:

ok answer is '113573943'

Test #10:

score: 0
Accepted
time: 71ms
memory: 7952kb

input:

23333333

output:

949849384

result:

ok answer is '949849384'

Test #11:

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

input:

102850434

output:

604886751

result:

ok answer is '604886751'

Test #12:

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

input:

998244353

output:

0

result:

ok answer is '0'

Test #13:

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

input:

1000000007

output:

318420284

result:

ok answer is '318420284'

Test #14:

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

input:

2147483547

output:

688759898

result:

ok answer is '688759898'

Test #15:

score: 0
Accepted
time: 94ms
memory: 10316kb

input:

5120103302

output:

116870489

result:

ok answer is '116870489'

Test #16:

score: 0
Accepted
time: 152ms
memory: 10132kb

input:

19834593299

output:

523663743

result:

ok answer is '523663743'

Test #17:

score: -100
Wrong Answer
time: 273ms
memory: 10020kb

input:

52500109238

output:

78396536

result:

wrong answer expected '195086665', found '78396536'