QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#579297#9309. GraphBob_WangTL 1387ms31784kbC++171.8kb2024-09-21 11:46:392024-09-21 11:46:40

Judging History

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

  • [2024-09-21 11:46:40]
  • 评测
  • 测评结果:TL
  • 用时:1387ms
  • 内存:31784kb
  • [2024-09-21 11:46:39]
  • 提交

answer

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

const int M=1000000;
const ll mod=998244353;
ll n,m;
ll tot,prime[maxn],mark[maxn];
ll cnt,id1[maxn],id2[maxn];//将区间映射到连续的数组
ll g[maxn],v[maxn],pre[maxn];
unordered_map<ll,ll>mp;

ll mul(ll x,ll y)
{
	if(y<0)
	return 1;
	x%=mod;
	ll ret=1;
	while(y)
	{
		if(y&1)
		ret=ret*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ret;
}

void ready(ll m)
{
	for(int i=2;i<=m;++i)
	{
		if(!mark[i])
		prime[++tot]=i;
		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(ll x)//求f(x)
{
	if(x==1)
	return 0;
	else
	return 1;
}

ll sumf(ll x)//求f(2)+...+f(x)的和
{
	return x-1;
}

void pre_solve(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(val);
	}
	for(ll j=1;j<=tot;++j)
	{
		ll x=prime[j];
		if(x*x>n)
		break;
		for(ll i=1;i<=cnt&&x*x<=v[i];++i)
		g[i]-=g[getnum(n,v[i]/x)]-(j-1);
	}
}

ll getprime(ll n)
{
	if(n<M)
	return pre[n];
	if(mp.count(n)!=0)
	return mp[n];
	cnt=0;
	m=sqrt(n);
	pre_solve(n);
	return mp[n]=g[getnum(n,n)];
}

int main()
{
	ready(M);
	for(int i=2;i<=M;++i)
	pre[i]=pre[i-1]+(1-mark[i]);
	scanf("%lld",&n);
	ll ans=1;
	for(ll l=1,r;l<=n;l=r+1)
	{
		r=n/(n/l);
		ll cnt=n/l,tot_p=(getprime(cnt)-getprime(cnt>>1))%mod;
		ll del;
		if(cnt>3)
		del=(cnt-tot_p-1)%mod*mul(cnt,tot_p)%mod;
		else del=mul(cnt,cnt-2);
		ans=ans*mul(del,r-l+1)%mod;
	}
	printf("%lld",ans);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 21224kb

input:

4

output:

8

result:

ok answer is '8'

Test #2:

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

input:

2

output:

1

result:

ok answer is '1'

Test #3:

score: 0
Accepted
time: 5ms
memory: 21436kb

input:

123

output:

671840470

result:

ok answer is '671840470'

Test #4:

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

input:

233

output:

353738465

result:

ok answer is '353738465'

Test #5:

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

input:

5981

output:

970246821

result:

ok answer is '970246821'

Test #6:

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

input:

86422

output:

897815688

result:

ok answer is '897815688'

Test #7:

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

input:

145444

output:

189843901

result:

ok answer is '189843901'

Test #8:

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

input:

901000

output:

819449452

result:

ok answer is '819449452'

Test #9:

score: 0
Accepted
time: 5ms
memory: 27652kb

input:

1000000

output:

113573943

result:

ok answer is '113573943'

Test #10:

score: 0
Accepted
time: 7ms
memory: 27844kb

input:

23333333

output:

949849384

result:

ok answer is '949849384'

Test #11:

score: 0
Accepted
time: 35ms
memory: 28320kb

input:

102850434

output:

604886751

result:

ok answer is '604886751'

Test #12:

score: 0
Accepted
time: 272ms
memory: 31784kb

input:

998244353

output:

0

result:

ok answer is '0'

Test #13:

score: 0
Accepted
time: 268ms
memory: 28192kb

input:

1000000007

output:

318420284

result:

ok answer is '318420284'

Test #14:

score: 0
Accepted
time: 573ms
memory: 30604kb

input:

2147483547

output:

688759898

result:

ok answer is '688759898'

Test #15:

score: 0
Accepted
time: 1387ms
memory: 30936kb

input:

5120103302

output:

116870489

result:

ok answer is '116870489'

Test #16:

score: -100
Time Limit Exceeded

input:

19834593299

output:


result: