[CodeForces]Educational Codeforces Round 138 (Rated for Div. 2)D. Counting Arrays(GCD)

发布于 2022-10-25  274 次阅读


题目链接:Problem - D - Codeforces

给定一个长度N,和一个取值范围M,现在要我们构造长度为[1, N],元素大小为[1, M]的数组,使得其被删除的方法大于1种,问构造方案数有多少。

删除方法定义为:对于数组中任意一个元素ai,如果gcd(ai, i) == 1,那么这个元素就可以被删除,删除之后,右边的所有元素向左移动,长度减1。

现在我们考虑任意一个数组,一定存在至少一种删除方式,那就是[1, 1, 1, ..., 1],不断的删除第一个元素直到删除干净,因为gcd(1, 任意自然数) = 1,所以可以保证这种方式一定合法。

既然我们要求大于1中的方案数,就可以用总方案数减去只有一种的方案数咯。

现在问题变为如何求删除方法只有[1, 1, 1, ..., 1]的数组的构造方案数。既然只能删第一位,说明任意时刻,i>1的位置上不能出现gcd(ai, i) == 1,也就是说ai和[2, i]的所有数字都要有非1的最大公因数,才能保证ai在左移到1位置之前没有办法被删除(如果某个时刻有办法被删除说明删除方法不止一种)。

现在就转化成一个质因数分解的问题,对于长度为i的序列,删除方法只有一种的序列构造方案数为M / [1, 1]的最小满足条件的数字 * M / [1, 2]的.... * M / [1, N]的。现在问题就是求这个最小满足条件的数字是多少,其实也不难求,设这个最小数字为mul,只要从1到i遍历求gcd(mul, i),如果gcd == 1,说明mul应该乘上这个数字。注意当mul < M后不要再操作了,因为M / mul肯定是等于0的,并且再乘容易爆。

特别需要注意的一点,mul是不能取模的,不然会丢失掉因子的信息。同时为了防止爆longlong,可以用龟速乘或开__int128。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int p = 998244353;

int gcd(int a,int b){return b == 0 ? a : gcd(b, a % b);}
int qmul(int a,int b)//龟速乘 
{
	int res = 0;
	while(b)
	{
		if(b & 1)res = (res + a) % p;
		a = (a + a) % p, b >>= 1;
	}
	return res;
}


signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int N, M;cin >> N >> M;
	int ans = 0, cnt = 1, dec = 1, mul = 1;
	for(int i = 1;i <= N; ++ i)
	{
		if(dec)
		{
			if(gcd(mul, i) == 1)
				if(mul <= M / i)mul = mul * i;
				else dec = 0;
			dec = qmul(dec, M / mul);
		}
		cnt = qmul(cnt, M);
		ans = ((ans + cnt - dec) % p + p) % p;
		
	} 
	cout << ans << '\n';
	return 0;
}

19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-10-25