QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#604932#8761. 另一个计数问题UESTC_OldEastWest#AC ✓1756ms37192kbC++172.1kb2024-10-02 14:39:222024-10-02 14:39:23

Judging History

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

  • [2024-10-02 14:39:23]
  • 评测
  • 测评结果：AC
  • 用时：1756ms
  • 内存：37192kb
查看
  • [2024-10-02 14:39:22]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include<cstdio>
#include<cmath>
#define ll long long
//#define ll __int128
#define maxn 1000005
using namespace std;

const int M=1000000;
const ll mod=998244353,inv2=499122177,inv6=166374059;
ll n,m;
ll tot,prime[maxn],mark[maxn];
ll cnt,id1[maxn],id2[maxn];//将区间映射到连续的数组
ll g[maxn],v[maxn],sum[2][maxn];

void ready(ll m)
{
	for(int i=2;i<=m;++i)
	{
		if(!mark[i])
		{
			prime[++tot]=i;
			sum[0][tot]=(sum[0][tot-1]+i)%mod;
			sum[1][tot]=(sum[1][tot-1]+1LL*i*i%mod)%mod;
		}
		for(int j=1;j<=tot;++j)
		{
			ll x=i*prime[j];
			if(x>M)
			break;
			mark[x]=1;
			if(i%prime[j]==0)
			break;
		}
	}
}

ll getnum(ll n,ll x)
{
	return (x<=m)?id1[x]:id2[n/x];
}

ll f(int fl,ll x)//求f(x)
{
	if(x==1)
	return 0;
	else
	{
		x%=mod;
		return (fl)?x%mod*x%mod:x%mod;
	}
}

ll sumf(int fl,ll x)//求f(2)+...+f(x)的和
{
	x%=mod;
	ll ret;
	if(fl)
	{
		ret=x%mod*(x+1)%mod*(2*x+1)%mod*inv6%mod;
		ret=(ret+mod-1)%mod;
	}
	else
	ret=(x+2)%mod*(x-1)%mod*inv2%mod;
	return ret;
}

void pre_solve(int fl,ll n)//预处理g数组
{
	for(ll l=1,r;l<=n;l=r+1)
	{
		r=n/(n/l);
		ll val=n/l;
		if(val<=m)
		id1[val]=++cnt;
		else id2[n/val]=++cnt;
		v[cnt]=val;
		g[cnt]=sumf(fl,val);
	}
	for(ll j=1;j<=tot;++j)
	{
		ll x=prime[j];
		for(ll i=1;i<=cnt&&x*x<=v[i];++i)
		{
			g[i]=(g[i]-f(fl,x)*((g[getnum(n,v[i]/x)]-sum[fl][j-1])%mod+mod)%mod)%mod;
			g[i]=(g[i]+mod)%mod;
		}
	}
}

ll getans(int fl,ll n)
{
	cnt=tot=0;
	m=sqrt(n);
	ready(m);
	pre_solve(fl,n);
	return g[getnum(n,n)];
}

int main()
{
	scanf("%lld",&n);
//	n=1e11;
	ll tot=(n+2)%mod*((n-1)%mod)%mod*inv2%mod;
	ll tot2=n%mod*((n+1)%mod)%mod*((2*n+1)%mod)%mod*inv6%mod;
	tot2=(tot2+mod-1)%mod;
	ll totp=((getans(0,n)-getans(0,n>>1))%mod+mod)%mod;
	ll totp2=((getans(1,n)-getans(1,n>>1))%mod+mod)%mod;
	ll ans=((tot*tot%mod-tot2)%mod+mod)%mod;
	ans=ans*inv2%mod;
	ans=((ans-totp*tot%mod)%mod+mod)%mod;
	ans=(ans+(((totp*totp%mod-totp2)%mod+mod)%mod*inv2%mod)+totp2)%mod;
	printf("%lld",ans);
	return 0;
}
/*
7
80
*/
源文件, 语言: C++17

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 14184kb

input:

4

output:

8

result:

ok 1 number(s): "8"

Test #2:

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

input:

5

output:

8

result:

ok 1 number(s): "8"

Test #3:

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

input:

6

output:

80

result:

ok 1 number(s): "80"

Test #4:

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

input:

7

output:

80

result:

ok 1 number(s): "80"

Test #5:

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

input:

8

output:

200

result:

ok 1 number(s): "200"

Test #6:

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

input:

9

output:

407

result:

ok 1 number(s): "407"

Test #7:

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

input:

10

output:

937

result:

ok 1 number(s): "937"

Test #8:

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

input:

79

output:

3224298

result:

ok 1 number(s): "3224298"

Test #9:

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

input:

123

output:

21077222

result:

ok 1 number(s): "21077222"

Test #10:

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

input:

158

output:

57411585

result:

ok 1 number(s): "57411585"

Test #11:

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

input:

285

output:

605750829

result:

ok 1 number(s): "605750829"

Test #12:

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

input:

355

output:

509863120

result:

ok 1 number(s): "509863120"

Test #13:

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

input:

484

output:

311440260

result:

ok 1 number(s): "311440260"

Test #14:

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

input:

520

output:

102191845

result:

ok 1 number(s): "102191845"

Test #15:

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

input:

706

output:

300787918

result:

ok 1 number(s): "300787918"

Test #16:

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

input:

747

output:

505062591

result:

ok 1 number(s): "505062591"

Test #17:

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

input:

784

output:

181810798

result:

ok 1 number(s): "181810798"

Test #18:

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

input:

76879

output:

716166793

result:

ok 1 number(s): "716166793"

Test #19:

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

input:

209295

output:

753032272

result:

ok 1 number(s): "753032272"

Test #20:

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

input:

220895

output:

874612082

result:

ok 1 number(s): "874612082"

Test #21:

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

input:

243390

output:

68635874

result:

ok 1 number(s): "68635874"

Test #22:

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

input:

414767

output:

862578797

result:

ok 1 number(s): "862578797"

Test #23:

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

input:

431662

output:

231728766

result:

ok 1 number(s): "231728766"

Test #24:

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

input:

521130

output:

106207351

result:

ok 1 number(s): "106207351"

Test #25:

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

input:

668419

output:

580625063

result:

ok 1 number(s): "580625063"

Test #26:

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

input:

700378

output:

790849562

result:

ok 1 number(s): "790849562"

Test #27:

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

input:

965876

output:

856082142

result:

ok 1 number(s): "856082142"

Test #28:

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

input:

998244350

output:

539142456

result:

ok 1 number(s): "539142456"

Test #29:

score: 0
Accepted
time: 66ms
memory: 24524kb

input:

998244351

output:

730264865

result:

ok 1 number(s): "730264865"

Test #30:

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

input:

998244352

output:

326703895

result:

ok 1 number(s): "326703895"

Test #31:

score: 0
Accepted
time: 68ms
memory: 24528kb

input:

998244353

output:

326703895

result:

ok 1 number(s): "326703895"

Test #32:

score: 0
Accepted
time: 65ms
memory: 22476kb

input:

998244354

output:

730264864

result:

ok 1 number(s): "730264864"

Test #33:

score: 0
Accepted
time: 68ms
memory: 20424kb

input:

998244355

output:

539142451

result:

ok 1 number(s): "539142451"

Test #34:

score: 0
Accepted
time: 68ms
memory: 22568kb

input:

998244356

output:

751581014

result:

ok 1 number(s): "751581014"

Test #35:

score: 0
Accepted
time: 114ms
memory: 22444kb

input:

2165916141

output:

216013547

result:

ok 1 number(s): "216013547"

Test #36:

score: 0
Accepted
time: 163ms
memory: 22624kb

input:

3550627266

output:

318019384

result:

ok 1 number(s): "318019384"

Test #37:

score: 0
Accepted
time: 384ms
memory: 24584kb

input:

11640239920

output:

137498099

result:

ok 1 number(s): "137498099"

Test #38:

score: 0
Accepted
time: 484ms
memory: 28760kb

input:

16191777349

output:

991399721

result:

ok 1 number(s): "991399721"

Test #39:

score: 0
Accepted
time: 786ms
memory: 28760kb

input:

31326230483

output:

99981147

result:

ok 1 number(s): "99981147"

Test #40:

score: 0
Accepted
time: 792ms
memory: 28824kb

input:

32810385543

output:

284259680

result:

ok 1 number(s): "284259680"

Test #41:

score: 0
Accepted
time: 865ms
memory: 30880kb

input:

37368395332

output:

511468046

result:

ok 1 number(s): "511468046"

Test #42:

score: 0
Accepted
time: 916ms
memory: 30960kb

input:

40002331093

output:

282851705

result:

ok 1 number(s): "282851705"

Test #43:

score: 0
Accepted
time: 1529ms
memory: 35044kb

input:

82884464396

output:

767050832

result:

ok 1 number(s): "767050832"

Test #44:

score: 0
Accepted
time: 1712ms
memory: 35256kb

input:

96506992785

output:

31413975

result:

ok 1 number(s): "31413975"

Test #45:

score: 0
Accepted
time: 1755ms
memory: 35144kb

input:

99999999995

output:

456189842

result:

ok 1 number(s): "456189842"

Test #46:

score: 0
Accepted
time: 1750ms
memory: 37192kb

input:

99999999996

output:

516138273

result:

ok 1 number(s): "516138273"

Test #47:

score: 0
Accepted
time: 1750ms
memory: 35136kb

input:

99999999997

output:

136420410

result:

ok 1 number(s): "136420410"

Test #48:

score: 0
Accepted
time: 1753ms
memory: 35132kb

input:

99999999998

output:

841974696

result:

ok 1 number(s): "841974696"

Test #49:

score: 0
Accepted
time: 1747ms
memory: 35196kb

input:

99999999999

output:

164762165

result:

ok 1 number(s): "164762165"

Test #50:

score: 0
Accepted
time: 1756ms
memory: 37184kb

input:

100000000000

output:

627965619

result:

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

伺服器時間: 2025-01-21 07:23:12 | 開源專案