UVA1434 YAPTCHA 题解

UVA1434 YAPTCHA 题解老师才讲了这道题就趁热打铁写篇题解。文章目录UVA1434 YAPTCHA 题解零、前置知识一、思考过程二、本题做法零、前置知识威尔逊定理若p pp是一个质数那么必定有( p − 1 ) ! ≡ − 1 ( m o d p ) (p-1)! \equiv -1 \pmod{p}(p−1)!≡−1(modp)一、思考过程S n ∑ k 1 n [ ( 3 k 6 ) ! 1 3 k 7 − [ ( 3 k 6 ) ! 3 k 7 ] ] S_n \sum_{k1}^n \left[ \frac{(3k6)! 1}{3k 7} - \left[ \frac{(3k6)!}{3k 7} \right] \right]Sn​k1∑n​[3k7(3k6)!1​−[3k7(3k6)!​]]这道题给了一个看起来很难的式子让我们求它的值。我们再仔细观察一下容易发现3 k 6 ( 3 k 7 ) − 1 3k 6 (3k 7) - 13k6(3k7)−1那么我们不妨设3 k 7 p 3k 7 p3k7p则3 k 6 p − 1 3k 6 p - 13k6p−1则原式可表达为S n ∑ k 1 n [ ( p − 1 ) ! 1 p − [ ( p − 1 ) ! p ] ] S_n \sum_{k1}^n \left[ \frac{(p - 1)! 1}{p} - \left[ \frac{(p - 1)!}{p} \right] \right]Sn​k1∑n​[p(p−1)!1​−[p(p−1)!​]]我们就可以用分类讨论p pp为质数容易发现p pp为质数是满足威尔逊定理( p − 1 ) ! ≡ − 1 ( m o d p ) (p-1)! \equiv -1 \pmod{p}(p−1)!≡−1(modp)即( p − 1 ) ! 1 q × p ( q ∈ Z ) ( p − 1 ) ! q × p − 1 ( q ∈ Z ) (p - 1)! 1 q \times p(q \in \mathbb{Z})\\ (p - 1)! q \times p-1(q \in \mathbb{Z})(p−1)!1q×p(q∈Z)(p−1)!q×p−1(q∈Z)那么( p − 1 ) ! 1 p − ( p − 1 ) ! p q × p p − q × p − 1 p q − ( q − 1 p ) ∴ q − 1 q − 1 p q ∴ q − ( q − 1 p ) q − ( q − 1 ) 1 \begin{align} \frac{(p - 1)! 1}{p} - \frac{(p - 1)!}{p} \frac{q \times p}{p} - \frac{q \times p - 1}{p} \nonumber\\ q - (q - \frac{1}{p}) \nonumber \end{align}\\ \therefore q - 1 q - \frac{1}{p} q\\ \therefore q - (q - \frac{1}{p}) q - (q - 1) 1p(p−1)!1​−p(p−1)!​​pq×p​−pq×p−1​q−(q−p1​)​∴q−1q−p1​q∴q−(q−p1​)q−(q−1)1答案就加一。p pp为合数证明p ∣ ( p − 1 ) ! p \mid (p - 1)!p∣(p−1)!其中p ≥ 10 p \ge 10p≥10:令p a × b , ( 1 a b ) p a \times b,(1 a b)pa×b,(1ab)① a ≠ b ①a \ne b①ab( p − 1 ) ! 1 × 2 × 3 × ⋯ × a × ⋯ × b × ⋯ × ( p − 1 ) (p-1)! 1\times2\times3\times\dots\times a\times\dots\times b\times\dots\times (p - 1)(p−1)!1×2×3×⋯×a×⋯×b×⋯×(p−1)显然( a × b ) ∣ ( p − 1 ) ! (a\times b) \mid(p-1)!(a×b)∣(p−1)!。② a b 且 a , b 是质数 ②a b \text{且} a, b \text{ 是质数}②ab且a,b是质数∴ a 2 ∴ a × b a 2 2 × a 又 ∵ k 4 ∴ ( p − 1 ) ! 1 × 2 × ⋯ × a × ⋯ × ( 2 × a ) × ⋯ × ( p − 1 ) \therefore a 2\\ \therefore a \times b a ^ 2 2 \times a\\ \text{又}\because k 4\\ \therefore (p-1)!1\times2\times\dots\times a\times\dots\times (2 \times a) \times\dots\times (p - 1)∴a2∴a×ba22×a又∵k4∴(p−1)!1×2×⋯×a×⋯×(2×a)×⋯×(p−1)同样有( a × b ) ∣ ( p − 1 ) ! (a\times b) \mid(p-1)!(a×b)∣(p−1)!。综上如果p pp为合数则p ∣ ( p − 1 ) ! p \mid (p - 1)!p∣(p−1)!那么( p − 1 ) ! 1 p − ( p − 1 ) ! p 0 − 0 0 \begin{align} \frac{(p - 1)! 1}{p} - \frac{(p - 1)!}{p} 0 - 0 0 \nonumber \end{align}p(p−1)!1​−p(p−1)!​0−00​答案就加零。综上所述当p pp为质数时答案加1 11当p pp为合数时答案加0 00。二、本题做法挨个遍历判断3 k 7 3k 73k7为质数还是合数当3 k 7 3k 73k7为质数时答案加1 11当3 k 7 3k 73k7为合数时答案加0 00。问题转化为有多少个k ∈ [ 1 , n ] k\in[1,n]k∈[1,n]满足3 k 7 3k 73k7是质数。代码就不给了。完结撒花|||||||||||||||||||||⎛⎝≥⏝⏝≤⎛⎝