牛客contest5666-J
传送门 题目大意： [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/07/equation-1024x94.png 答案一定是一个有理数，以n=p·q-1的形式并模上998244353给出。 q-1 表示q的逆元，可以用扩欧或费马小定理来算。 如果p是一个质数，而整数a不是p的倍数，则有a(p-1)≡1(mod p) 费马小定理 有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是显然地。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解，它可以用来计算模反元素(也叫模逆元)。扩展欧几里得算法 [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/07/IMG_390520200714-224509-1024x931.jpg ```cpp #include using namespace std; typedef long long ll; int const LIM = 2e6 + 5; int const MOD = 998244353; ll n; ll fac[LIM]; ll qmod(ll …