给定一个长度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;
}
文章评论