题目太生草了，我给读者们简化一下。 给定一个长 N + 1 N+1 N+1 的序列 a a a 的第 N + 1 N+1 N+1 位，求满足 ∑ i = 1 n a i ⋅ x i + M ⋅ x n + 1 = 1 \sum_{i=1}^{n}a_i·x_i+M·x_{n+1}=1 ∑i=1nai⋅xi+M⋅xn+1=1 ( x i ∈ Z ) (x_i\in \mathbb{Z}) (xi∈Z) 的序列 a a a 有多少个。
我把我比赛时的思路说说，可能能帮助理解。 首先看到 N = 1 N=1 N=1 的情况，即 a 1 x 1 + M x 2 = 1 a_1x_1+Mx_2=1 a1x1+Mx2=1 ，诶，这不就是bezout定理吗？那么我们就保证 g c d ( a 1 , M ) = 1 gcd(a_1,M)=1 gcd(a1,M)=1 就行了吗？ 然后我就大胆猜想这是不是能够推广到更多的情况呢？，然后我看看了样例解释的几个数据，欸？好像的确是诶。 接着，我就打了个暴力去看看这东西对不对，试了一下 N = 8 N=8 N=8 与 M = 8 M=8 M=8 的样例，诶，过了，然后我就往后继续推了。 接下来 M M M 为质数，我简单推了一下，发现的确挺简单。你想嘛，我们有 N N N个位置给你用，每个位置又有 M M M种选择，那么，总方案数就是 M N M^N MN，然后再减去不符合的方案，即1.为什么呢？其实啊，因为1~M-1中无论选哪一个都会使得整个的gcd为1.那么只要不是全部都是M的情况就可以了。 然后我再看，M为质数的幂，然后往组合数方面想，结果发现不对…只好通过打表找规律，找了半天，发现了一个这样的规律：设 M = p e M=p^e M=pe ，则不符合情况的=当 M M M为 p p p时的情况 × \times × p n ( e − 1 ) p^{n(e-1)} pn(e−1) 即 ( p n − 1 ) × p n ( e − 1 ) (p^n-1)\times p^{n(e-1)} (pn−1)×pn(e−1)，然后就这么完成了80分的做法。 其实100分的做法也不算很难（比赛时没有推出来），先把我推出来的那个公式化简一下，就变成了 M N − ( M p ) N M^N-(\frac{M}{p})^N MN−(pM)N但推广起来我们发现减多了，然后发现这其实就是容斥原理，这就没了，具体实现见代码。
