QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#766604#9553. The Hermitwowlie#WA 153ms7380kbC++201.8kb2024-11-20 17:55:492024-11-20 17:55:52

Judging History

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

  • [2024-11-20 17:55:52]
  • 评测
  • 测评结果:WA
  • 用时:153ms
  • 内存:7380kb
  • [2024-11-20 17:55:49]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;

const LL N=100010,mod=998244353;

LL primes[N],minp[N],idx;
bool st[N];

void is_primes(LL n)
{
	for(LL i=2;i<=n;i++)
	{
		if(!st[i])primes[idx++]=i,minp[i]=i;
		for(LL j=0;i*primes[j]<=n;j++)
		{
			st[i*primes[j]]=true;
			minp[i*primes[j]]=primes[j];
			if(i%primes[j]==0)break;
		}
	}
}

LL fact[N],infact[N];//fact表示阶乘,infact表示阶乘的逆元

LL qmi(LL a,LL b)
{
    LL res=1;
    while(b)
    {
        if(b&1)res=(LL)res*a%mod;
        a=(LL)a*a%mod;
        b>>=1;
    }
    return res;
}

void init()
{
	fact[0]=infact[0]=1;
    for(LL i=1;i<N;i++)
    {
        fact[i]=(LL)fact[i-1]*i%mod;
        infact[i]=(LL)infact[i-1]*qmi(i,mod-2)%mod;
    }
}

LL query(LL a,LL b)
{
	LL res=(LL)fact[a]*infact[b]%mod*infact[a-b]%mod;
	return res;
}

void solve()
{
	LL n,m;
	cin>>n>>m;

	LL res=0;
	for(LL i=1;i<=n;i++)
	{
		map<LL,LL>mp;
		for(LL j=i;j<=n;j+=i)
		{
			LL val=j/i;
			while(val!=minp[val]&&val!=1)
			{
				LL t=minp[val];
				mp[t]++;
				while(val%t==0)val/=t;
			}
			if(val!=1)mp[val]++;
		} 

		LL t=0;
		if(n/i-1>=m)t=query(n/i-1,m);
		for(auto [u,v]:mp)
		{
			if(v>=m)t=(t-query(v,m)%mod+mod)%mod;
		}
		res=(res+t*m%mod)%mod;

		LL cnt=0;
		for(LL j=1;j*j<=i;j++)
		{
			if(i%j==0)
			{
				if(j!=i/j)cnt+=2;
				else cnt++;
			}
		}

		for(LL j=1;j<=cnt;j++)
		{
			LL val=0;
			if(n/i-1>=m-j)val=query(n/i-1,m-j);
			for(auto [u,v]:mp)
			{
				if(v>=m-j)val=(val-query(v,m-j)%mod+mod)%mod;
			}
			res=(res+query(cnt,j)*val%mod*(m-j)%mod)%mod;
		}
	}
	cout<<res<<endl;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	LL T;
	T=1;
	init();
	is_primes(1e5);
	while(T--)
	{
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 12ms
memory: 6288kb

input:

4 3

output:

7

result:

ok 1 number(s): "7"

Test #2:

score: 0
Accepted
time: 13ms
memory: 6076kb

input:

11 4

output:

1187

result:

ok 1 number(s): "1187"

Test #3:

score: 0
Accepted
time: 153ms
memory: 7380kb

input:

100000 99999

output:

17356471

result:

ok 1 number(s): "17356471"

Test #4:

score: 0
Accepted
time: 21ms
memory: 6220kb

input:

11451 1919

output:

845616153

result:

ok 1 number(s): "845616153"

Test #5:

score: -100
Wrong Answer
time: 153ms
memory: 6736kb

input:

99998 12345

output:

284096349

result:

wrong answer 1st numbers differ - expected: '936396560', found: '284096349'