QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#700290#9515. 无限地狱TheZone100 ✓1913ms107660kbC++235.1kb2024-11-02 12:39:172024-11-02 12:39:21

Judging History

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

  • [2024-11-02 12:39:21]
  • 评测
  • 测评结果：100
  • 用时：1913ms
  • 内存：107660kb
查看
  • [2024-11-02 12:39:17]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 3000000
#define M 400000
#define mod 998244353
using namespace std;
long long read()
{
	char c=0;
	long long sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int MD(int x)
{
	return x>=mod?x-mod:x;
}
int MD2(int x)
{
	return x<0?x+mod:x;
}
void Adder(int &x,int d)
{
	x=x+d>=mod?x+d-mod:x+d;
	return;
}
void Adder2(int &x,int d)
{
	x=x+d<0?x+d+mod:x+d;
	return;
}
long long n,tong[M+1];
int length,sn,dp[N+1],DP[N+1],zdp[N+1],zDP[N+1],pw[N+1],pw2[N+1],miu[N+1],smiu[N+1],wdp[M+1],wDP[M+1],tmiu[M+1];
bool nprime[N+1];
int get_pow(long long x)
{
	return 1ll*pw[(x-1)%N+1]*pw2[(x-1)/N]%mod;
}
int S(long long x)
{
	if (x&1) return MD2(get_pow((x>>1)+1)-(x+1)%mod);
    else return MD2(3ll*get_pow((x>>1)-1)%mod-(x+1)%mod);
}
int get(long long x)
{
	if (x<=sn) return x;
	else return length-n/x+1;
}
int main()
{
	n=read();
	while (1ll*(sn+1)*(sn+1)<=n) ++sn;
	for (long long i=1,lst;i<=n;i=lst+1) lst=n/(n/i),tong[++length]=n/i;
	reverse(tong+1,tong+length+1);
	for (int i=1;i<=N;++i) miu[i]=1;
	for (int i=2;i<=N;++i)
		if (!nprime[i])
		{
			miu[i]=-1;
			for (int j=(i<<1);j<=N;j+=i)
			{
				miu[j]=-miu[j],nprime[j]=1;
				if ((j/i)%i==0) miu[j]=0;
			}
		}
	pw[0]=pw2[0]=1;
	for (int i=1;i<=N;++i) smiu[i]=MD2(smiu[i-1]+miu[i]),pw[i]=2ll*pw[i-1]%mod;
	for (int i=1;i<=N;++i) pw2[i]=1ll*pw2[i-1]*pw[N]%mod;
	for (int i=1;i<=N;++i)
	{
		Adder(zdp[i],zdp[i-1]),Adder(zDP[i],zDP[i-1]),Adder(dp[i],zdp[i]),Adder(DP[i],zDP[i]),Adder(dp[i],pw[i-1]),Adder(DP[i],MD2(dp[i]-1));
		for (int j=2;j<=N/i;++j)
		{
			Adder(zdp[i*j],DP[i]),Adder(zdp[i*j],1ll*MD2(pw[(j>>1)-1]-1)*MD2(2ll*MD(dp[i]+DP[i])%mod-1)%mod);
			if (miu[j]==1) Adder(zDP[i*j],MD2(3ll*dp[i]%mod-2));
			else if (miu[j]==-1) Adder2(zDP[i*j],-MD2(3ll*dp[i]%mod-2));
			if ((i+1)*j<=N)
			{
				Adder2(zdp[(i+1)*j],-DP[i]),Adder2(zdp[(i+1)*j],-1ll*MD2(pw[(j>>1)-1]-1)*MD2(2ll*MD(dp[i]+DP[i])%mod-1)%mod);
				if (miu[j]==1) Adder2(zDP[(i+1)*j],-MD2(3ll*dp[i]%mod-2));
				else if (miu[j]==-1) Adder(zDP[(i+1)*j],MD2(3ll*dp[i]%mod-2));
			}
		}
	}
	for (int i=1;i<=length;++i)
	{
		if (tong[i]<=N) wdp[i]=dp[tong[i]],wDP[i]=DP[tong[i]],tmiu[i]=smiu[tong[i]];
		else
		{
			wdp[i]=get_pow(tong[i]-1),tmiu[i]=1;
			for (long long j=2,lst;j<=tong[i];j=lst+1)
			{
				lst=tong[i]/(tong[i]/j);
				Adder2(tmiu[i],-1ll*((lst-j+1)%mod)*tmiu[get(tong[i]/j)]%mod);
				Adder(wdp[i],1ll*((lst-j+1)%mod)*wDP[get(tong[i]/j)]%mod);
				Adder(wdp[i],1ll*MD2(S(lst)-S(j-1))%mod*MD2(2ll*MD(wdp[get(tong[i]/j)]+wDP[get(tong[i]/j)])%mod-1)%mod);
				Adder(wDP[i],1ll*MD2(tmiu[get(lst)]-tmiu[get(j-1)])%mod*MD2(3ll*wdp[get(tong[i]/j)]%mod-2)%mod);
			}
			Adder(wDP[i],MD2(wdp[i]-1));
		}
	}
	printf("%d\n",wdp[length]);
	return 0;
}
/*#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 3000000
#define M 400000
#define mod 998244353
using namespace std;
long long read()
{
	char c=0;
	long long sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int MD(int x)
{
	return x>=mod?x-mod:x;
}
int MD2(int x)
{
	return x<0?x+mod:x;
}
void Adder(int &x,int d)
{
	x=x+d>=mod?x+d-mod:x+d;
	return;
}
void Adder2(int &x,int d)
{
	x=x+d<0?x+d+mod:x+d;
	return;
}
long long n,tong[M+1];
int length,sn,dp[N+1],DP[N+1],zdp[N+1],zDP[N+1],pw[N+1],pw2[N+1],miu[N+1],smiu[N+1],wdp[M+1],wDP[M+1],tmiu[M+1];
bool nprime[N+1];
int get_pow(long long x)
{
	return 1ll*pw[(x-1)%N+1]*pw2[(x-1)/N]%mod;
}
int S(long long x)
{
	if (x&1) return MD2(get_pow((x>>1)+1)-(x+1)%mod);
    else return MD2(3ll*get_pow((x>>1)-1)%mod-(x+1)%mod);
}
int get(long long x)
{
	if (x<=sn) return x;
	else return length-n/x+1;
}
int main()
{
	n=read();
	while (1ll*(sn+1)*(sn+1)<=n) ++sn;
	for (long long i=1,lst;i<=n;i=lst+1) lst=n/(n/i),tong[++length]=n/i;
	reverse(tong+1,tong+length+1);
	for (int i=1;i<=N;++i) miu[i]=1;
	for (int i=2;i<=N;++i)
		if (!nprime[i])
		{
			miu[i]=-1;
			for (int j=(i<<1);j<=N;j+=i)
			{
				miu[j]=-miu[j],nprime[j]=1;
				if ((j/i)%i==0) miu[j]=0;
			}
		}
	pw[0]=pw2[0]=1;
	for (int i=1;i<=N;++i) smiu[i]=MD2(smiu[i-1]+miu[i]),pw[i]=2ll*pw[i-1]%mod;
	for (int i=1;i<=N;++i) pw2[i]=1ll*pw2[i-1]*pw[N]%mod;
	for (int i=1;i<=N;++i)
	{
		Adder(zdp[i],zdp[i-1]),Adder(zDP[i],zDP[i-1]),Adder(dp[i],zdp[i]),Adder(DP[i],zDP[i]),Adder(dp[i],pw[i-1]),Adder(DP[i],MD2(dp[i]-1));
		for (int j=2;j<=N/i;++j)
		{
			Adder(zdp[i*j],DP[i]),Adder(zdp[i*j],1ll*MD2(pw[(j>>1)-1]-1)*MD2(2ll*MD(dp[i]+DP[i])%mod-1)%mod);
			if (miu[j]==1) Adder(zDP[i*j],MD2(3ll*dp[i]%mod-2));
			else if (miu[j]==-1) Adder2(zDP[i*j],-MD2(3ll*dp[i]%mod-2));
			if ((i+1)*j<=N)
			{
				Adder2(zdp[(i+1)*j],-DP[i]),Adder2(zdp[(i+1)*j],-1ll*MD2(pw[(j>>1)-1]-1)*MD2(2ll*MD(dp[i]+DP[i])%mod-1)%mod);
				if (miu[j]==1) Adder2(zDP[(i+1)*j],-MD2(3ll*dp[i]%mod-2));
				else if (miu[j]==-1) Adder(zDP[(i+1)*j],MD2(3ll*dp[i]%mod-2));
			}
		}
	}
	}
	printf("%d\n",wdp[length]);
	return 0;
}
*/
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 544ms
memory: 105340kb

input:

6

output:

38

result:

ok 1 number(s): "38"

Test #2:

score: 4
Accepted
time: 540ms
memory: 104200kb

input:

7

output:

73

result:

ok 1 number(s): "73"

Test #3:

score: 4
Accepted
time: 541ms
memory: 103496kb

input:

8

output:

148

result:

ok 1 number(s): "148"

Test #4:

score: 4
Accepted
time: 539ms
memory: 104828kb

input:

9

output:

284

result:

ok 1 number(s): "284"

Test #5:

score: 4
Accepted
time: 541ms
memory: 104772kb

input:

10

output:

565

result:

ok 1 number(s): "565"

Subtask #2:

score: 13
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 13
Accepted
time: 548ms
memory: 103484kb

input:

30

output:

536938322

result:

ok 1 number(s): "536938322"

Test #7:

score: 13
Accepted
time: 571ms
memory: 103672kb

input:

35

output:

210046687

result:

ok 1 number(s): "210046687"

Test #8:

score: 13
Accepted
time: 564ms
memory: 103808kb

input:

38

output:

680532913

result:

ok 1 number(s): "680532913"

Test #9:

score: 13
Accepted
time: 538ms
memory: 104780kb

input:

39

output:

362030079

result:

ok 1 number(s): "362030079"

Test #10:

score: 13
Accepted
time: 527ms
memory: 104904kb

input:

40

output:

723529503

result:

ok 1 number(s): "723529503"

Subtask #3:

score: 17
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 17
Accepted
time: 550ms
memory: 105064kb

input:

2000

output:

686289840

result:

ok 1 number(s): "686289840"

Test #12:

score: 17
Accepted
time: 535ms
memory: 103236kb

input:

2500

output:

672176744

result:

ok 1 number(s): "672176744"

Test #13:

score: 17
Accepted
time: 544ms
memory: 104496kb

input:

2998

output:

77001108

result:

ok 1 number(s): "77001108"

Test #14:

score: 17
Accepted
time: 556ms
memory: 104064kb

input:

2999

output:

337824775

result:

ok 1 number(s): "337824775"

Test #15:

score: 17
Accepted
time: 541ms
memory: 103564kb

input:

3000

output:

636156660

result:

ok 1 number(s): "636156660"

Subtask #4:

score: 21
Accepted

Dependency #3:

100%
Accepted

Test #16:

score: 21
Accepted
time: 549ms
memory: 104188kb

input:

100000

output:

809175948

result:

ok 1 number(s): "809175948"

Test #17:

score: 21
Accepted
time: 543ms
memory: 103860kb

input:

200000

output:

425311829

result:

ok 1 number(s): "425311829"

Test #18:

score: 21
Accepted
time: 556ms
memory: 103376kb

input:

500000

output:

302623178

result:

ok 1 number(s): "302623178"

Test #19:

score: 21
Accepted
time: 543ms
memory: 105224kb

input:

900000

output:

683174559

result:

ok 1 number(s): "683174559"

Test #20:

score: 21
Accepted
time: 562ms
memory: 104620kb

input:

1000000

output:

126560600

result:

ok 1 number(s): "126560600"

Subtask #5:

score: 22
Accepted

Dependency #4:

100%
Accepted

Test #21:

score: 22
Accepted
time: 550ms
memory: 104644kb

input:

100000000

output:

269652149

result:

ok 1 number(s): "269652149"

Test #22:

score: 22
Accepted
time: 600ms
memory: 103992kb

input:

300000000

output:

421051808

result:

ok 1 number(s): "421051808"

Test #23:

score: 22
Accepted
time: 590ms
memory: 104808kb

input:

700000000

output:

834273337

result:

ok 1 number(s): "834273337"

Test #24:

score: 22
Accepted
time: 631ms
memory: 107304kb

input:

990000000

output:

848544380

result:

ok 1 number(s): "848544380"

Test #25:

score: 22
Accepted
time: 613ms
memory: 104840kb

input:

1000000000

output:

341773916

result:

ok 1 number(s): "341773916"

Subtask #6:

score: 23
Accepted

Dependency #5:

100%
Accepted

Test #26:

score: 23
Accepted
time: 1357ms
memory: 107652kb

input:

12000000000

output:

877921487

result:

ok 1 number(s): "877921487"

Test #27:

score: 23
Accepted
time: 1655ms
memory: 106652kb

input:

17000000000

output:

691116504

result:

ok 1 number(s): "691116504"

Test #28:

score: 23
Accepted
time: 1910ms
memory: 107660kb

input:

19900000000

output:

87007717

result:

ok 1 number(s): "87007717"

Test #29:

score: 23
Accepted
time: 1913ms
memory: 107360kb

input:

19990000000

output:

455948458

result:

ok 1 number(s): "455948458"

Test #30:

score: 23
Accepted
time: 1885ms
memory: 107268kb

input:

20000000000

output:

128153394

result:

ok 1 number(s): "128153394"
English 繁體中文 简体中文

Server Time: 2025-02-02 04:52:57 | OpenSource Project