QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#766553#9553. The Hermitwowlie#WA 129ms5536kbC++201.8kb2024-11-20 17:43:192024-11-20 17:43:20

Judging History

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

  • [2024-11-20 17:43:20]
  • 评测
  • 测评结果:WA
  • 用时:129ms
  • 内存:5536kb
  • [2024-11-20 17:43:19]
  • 提交

answer

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

const int N=100010,mod=998244353;

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

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

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

int qmi(int a,int b)
{
    int 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(int 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(int a,int b)
{
	LL res=(LL)fact[a]*infact[b]%mod*infact[a-b]%mod;
	return res;
}

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

	LL res=0;
	for(int i=1;i<=n;i++)
	{
		map<int,int>mp;
		for(int j=i;j<=n;j+=i)
		{
			int val=j/i;
			while(val!=minp[val]&&val!=1)
			{
				int 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-=query(v,m);
		}
		res=(res+t*m%mod)%mod;

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

		for(int 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-=query(v,m-j);
			}
			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);

	int 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: 14ms
memory: 4808kb

input:

4 3

output:

7

result:

ok 1 number(s): "7"

Test #2:

score: 0
Accepted
time: 14ms
memory: 4856kb

input:

11 4

output:

1187

result:

ok 1 number(s): "1187"

Test #3:

score: 0
Accepted
time: 126ms
memory: 5324kb

input:

100000 99999

output:

17356471

result:

ok 1 number(s): "17356471"

Test #4:

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

input:

11451 1919

output:

845616153

result:

ok 1 number(s): "845616153"

Test #5:

score: -100
Wrong Answer
time: 129ms
memory: 5536kb

input:

99998 12345

output:

284096349

result:

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