比赛链接

Educational Codeforces Round 138 (Rated for Div. 2)

D. Counting Arrays

解题思路

容斥原理

显然 \([1,1,\dots,1]\) 是一组方案，直接求不好求解，考虑反面，对于 \([2,3,\dots,n]\) 的数 \(x\)，如果 \(gcd(x,i)=1\) 则显然构造一组解，则要求 \(x\) 与 \(i\) 前面所有的素数都不互质，求出前面所有素数乘积 \(mul\)，这样的数共有 \(m/mul\) 个

中间有部分过程爆long long有点难受

• 时间复杂度：\(O(nlogn)\)

代码

// Problem: D. Counting Arrays
// Contest: Codeforces - Educational Codeforces Round 138 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1749/problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int mod=998244353;
int ksm(int a,int b,int p)
{
	int res=1%p;
	while(b)
	{
		if(b&1)res=(__int128)res*a%p;
		a=(__int128)a*a%p;
		b>>=1;
	}
	return res;
}
bool is(int x)
{
	for(int i=2;i<=x/i;i++)
		if(x%i==0)return false;
	return true;
}
signed main()
{
    int n,m,res=0,a=1,t=1,ot=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)res=(res+ksm(m,i,mod))%mod;
    for(int i=1;i<=n;i++)
    {
    	if(is(i))
    	{
    		if((__int128)a*i<=m)a*=i;
    		else
    			break;
    	}
    	t=(__int128)t*(m/a)%mod;
    	ot=(ot+t)%mod;
    }
    res-=ot;
    cout<<(res%mod+mod)%mod;
    return 0;
}