给定一个长度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; }
Comments NOTHING