C#版 - HDUoj 5391 - Zball in Tina Town(素数) - 题解
版权声明: 本文为博主Bravo Yeung(知乎UserName同名)的原创文章，欲转载请先私信获博主允许，转载时请附上网址
http://blog.csdn.net/lzuacm。
HDUoj 5391 - Zball in Tina Town
在线提交:
http://acm.hdu.edu.cn/showproblem.php?pid=5391
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 2790 Accepted Submission(s): 1309
题目大意：
Tina Town 是一个善良友好的地方, 这里的每一个人都互相关心。
Tina有一个球，它的名字叫zball。zball很神奇，它每天会变大一些。在第一天，它和原始大小一样。 在第二天，它的大小将成为第一天的2倍。 在第n天，它的大小将为第(n-1)天大小的n倍。Tina想知道，zball在第n-1天时的大小对n取模是多少呢？
思路：
陶哲轩在他的书Solving mathematical problems 中提到威尔逊定理 <nobr aria-hidden="true"> (n−1)!+1 (mod n)≡0⇔n </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mo stretchy="false"> ( </mo> <mi> n </mi> <mo> − </mo> <mn> 1 </mn> <mo stretchy="false"> ) </mo> <mo> ! </mo> <mo> + </mo> <mn> 1 </mn> <mtext> </mtext> <mo stretchy="false"> ( </mo> <mi> m </mi> <mi> o </mi> <mi> d </mi> <mtext> </mtext> <mi> n </mi> <mo stretchy="false"> ) </mo> <mo> ≡ </mo> <mn> 0 </mn> <mo stretchy="false"> ⇔ </mo> <mi> n </mi> </math> is prime.
首先，来回忆一下阶乘的定义:
<nobr aria-hidden="true"> m!=∏mk=1k=1×2×3×⋯×m. </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> m </mi> <mo> ! </mo> <mo> = </mo> <munderover> <mo> ∏ </mo> <mrow class="MJX-TeXAtom-ORD"> <mi> k </mi> <mo> = </mo> <mn> 1 </mn> </mrow> <mi> m </mi> </munderover> <mi> k </mi> <mo> = </mo> <mn> 1 </mn> <mo> × </mo> <mn> 2 </mn> <mo> × </mo> <mn> 3 </mn> <mo> × </mo> <mo> ⋯ </mo> <mo> × </mo> <mi> m </mi> <mo> . </mo> </math>
可得出结论: 存在a, b <nobr aria-hidden="true"> ∈ </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mo> ∈ </mo> </math> [1, m] 使得 <nobr aria-hidden="true"> a⋅b </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> a </mi> <mo> ⋅ </mo> <mi> b </mi> </math>能整除m!
假定 <nobr aria-hidden="true"> m=n−1 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> m </mi> <mo> = </mo> <mi> n </mi> <mo> − </mo> <mn> 1 </mn> </math>,
原问题可分类如下:
- n是质数，则由威尔逊定理知:
<nobr aria-hidden="true"> (n−1)! (mod n)=−1(mod n)=n−1 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mo stretchy="false"> ( </mo> <mi> n </mi> <mo> − </mo> <mn> 1 </mn> <mo stretchy="false"> ) </mo> <mo> ! </mo> <mtext> </mtext> <mo stretchy="false"> ( </mo> <mi> m </mi> <mi> o </mi> <mi> d </mi> <mtext> </mtext> <mi> n </mi> <mo stretchy="false"> ) </mo> <mo> = </mo> <mo> − </mo> <mn> 1 </mn> <mo stretchy="false"> ( </mo> <mi> m </mi> <mi> o </mi> <mi> d </mi> <mtext> </mtext> <mi> n </mi> <mo stretchy="false"> ) </mo> <mo> = </mo> <mi> n </mi> <mo> − </mo> <mn> 1 </mn> </math>. n是合数(composite)，且n不能表示为质数的平方，则 <nobr aria-hidden="true"> ∃a,b </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi mathvariant="normal"> ∃ </mi> <mi> a </mi> <mo> , </mo> <mi> b </mi> </math>使得 <nobr aria-hidden="true"> n=a⋅b | m! </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> n </mi> <mo> = </mo> <mi> a </mi> <mo> ⋅ </mo> <mi> b </mi> <mtext> </mtext> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false"> | </mo> </mrow> <mtext> </mtext> <mi> m </mi> <mo> ! </mo> </math>，即
<nobr aria-hidden="true"> a⋅b=n | (n−1)! </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> a </mi> <mo> ⋅ </mo> <mi> b </mi> <mo> = </mo> <mi> n </mi> <mtext> </mtext> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false"> | </mo> </mrow> <mtext> </mtext> <mo stretchy="false"> ( </mo> <mi> n </mi> <mo> − </mo> <mn> 1 </mn> <mo stretchy="false"> ) </mo> <mo> ! </mo> </math>n是合数，且n可表示成质数p的平方，而且 p > <nobr aria-hidden="true"> 2–√+1 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msqrt> <mn> 2 </mn> </msqrt> <mo> + </mo> <mn> 1 </mn> </math>, 即 <nobr aria-hidden="true"> p≥3 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> p </mi> <mo> ≥ </mo> <mn> 3 </mn> </math>
此时的目标是寻找a, b使得 <nobr aria-hidden="true"> a⋅b | p2 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> a </mi> <mo> ⋅ </mo> <mi> b </mi> <mtext> </mtext> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false"> | </mo> </mrow> <mtext> </mtext> <msup> <mi> p </mi> <mn> 2 </mn> </msup> </math>，不妨假设 a = <nobr aria-hidden="true"> k1⋅p </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> k </mi> <mn> 1 </mn> </msub> <mo> ⋅ </mo> <mi> p </mi> </math>, b = <nobr aria-hidden="true"> k2⋅p </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> k </mi> <mn> 2 </mn> </msub> <mo> ⋅ </mo> <mi> p </mi> </math>.
<nobr aria-hidden="true"> n=p2 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> n </mi> <mo> = </mo> <msup> <mi> p </mi> <mn> 2 </mn> </msup> </math>, 则n的约数有 <nobr aria-hidden="true"> 1,p,p2 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mn> 1 </mn> <mo> , </mo> <mi> p </mi> <mo> , </mo> <msup> <mi> p </mi> <mn> 2 </mn> </msup> </math>.
下面用反证法来证明为何a、b均与p线性相关，如果a( <nobr aria-hidden="true"> ≥1 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mo> ≥ </mo> <mn> 1 </mn> </math>)与p线性无关，则 <nobr aria-hidden="true"> b=k⋅p2≥p2(k≥1) </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> b </mi> <mo> = </mo> <mi> k </mi> <mo> ⋅ </mo> <msup> <mi> p </mi> <mn> 2 </mn> </msup> <mo> ≥ </mo> <msup> <mi> p </mi> <mn> 2 </mn> </msup> <mo stretchy="false"> ( </mo> <mi> k </mi> <mo> ≥ </mo> <mn> 1 </mn> <mo stretchy="false"> ) </mo> </math>，而 <nobr aria-hidden="true"> b≤m=n−1=p2−1 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> b </mi> <mo> ≤ </mo> <mi> m </mi> <mo> = </mo> <mi> n </mi> <mo> − </mo> <mn> 1 </mn> <mo> = </mo> <msup> <mi> p </mi> <mn> 2 </mn> </msup> <mo> − </mo> <mn> 1 </mn> </math>，矛盾。同理假设b与p线性无关也会出现同样的矛盾，因此a、b均与p线性相关。<nobr aria-hidden="true"> 1≤a=k1⋅p<b=k2⋅p≤p2−1 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mn> 1 </mn> <mo> ≤ </mo> <mi> a </mi> <mo> = </mo> <msub> <mi> k </mi> <mn> 1 </mn> </msub> <mo> ⋅ </mo> <mi> p </mi> <mo> < </mo> <mi> b </mi> <mo> = </mo> <msub> <mi> k </mi> <mn> 2 </mn> </msub> <mo> ⋅ </mo> <mi> p </mi> <mo> ≤ </mo> <msup> <mi> p </mi> <mn> 2 </mn> </msup> <mo> − </mo> <mn> 1 </mn> </math>
让a尽量小, 则 <nobr aria-hidden="true"> k1=1 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub> <mi> k </mi> <mn> 1 </mn> </msub> <mo> = </mo> <mn> 1 </mn> </math>, 令 <nobr aria-hidden="true"> t=k2 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> t </mi> <mo> = </mo> <msub> <mi> k </mi> <mn> 2 </mn> </msub> </math>, 于是b可表示为 <nobr aria-hidden="true"> t⋅p </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> t </mi> <mo> ⋅ </mo> <mi> p </mi> </math>.
<nobr aria-hidden="true"> ∴t⋅p≤p2−1 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mo> ∴ </mo> <mi> t </mi> <mo> ⋅ </mo> <mi> p </mi> <mo> ≤ </mo> <msup> <mi> p </mi> <mn> 2 </mn> </msup> <mo> − </mo> <mn> 1 </mn> </math>
解上述不等式可得 <nobr aria-hidden="true"> p≥t+t2+4√2=f(t) (t≥2) </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> p </mi> <mo> ≥ </mo> <mfrac> <mrow> <mi> t </mi> <mo> + </mo> <msqrt> <msup> <mi> t </mi> <mn> 2 </mn> </msup> <mo> + </mo> <mn> 4 </mn> </msqrt> </mrow> <mn> 2 </mn> </mfrac> <mo> = </mo> <mi> f </mi> <mo stretchy="false"> ( </mo> <mi> t </mi> <mo stretchy="false"> ) </mo> <mtext> </mtext> <mo stretchy="false"> ( </mo> <mi> t </mi> <mo> ≥ </mo> <mn> 2 </mn> <mo stretchy="false"> ) </mo> </math>, 容易分析得f(t)是递增函数。
当 <nobr aria-hidden="true"> t=2 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> t </mi> <mo> = </mo> <mn> 2 </mn> </math>时, <nobr aria-hidden="true"> p≥2–√+1 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> p </mi> <mo> ≥ </mo> <msqrt> <mn> 2 </mn> </msqrt> <mo> + </mo> <mn> 1 </mn> </math>，即 <nobr aria-hidden="true"> p∈[2–√+1,+∞) </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> p </mi> <mo> ∈ </mo> <mo stretchy="false"> [ </mo> <msqrt> <mn> 2 </mn> </msqrt> <mo> + </mo> <mn> 1 </mn> <mo> , </mo> <mo> + </mo> <mi mathvariant="normal"> ∞ </mi> <mo stretchy="false"> ) </mo> </math>, 于是 <nobr aria-hidden="true"> b=2⋅p </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> b </mi> <mo> = </mo> <mn> 2 </mn> <mo> ⋅ </mo> <mi> p </mi> </math>.
而当 <nobr aria-hidden="true"> t>2 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> t </mi> <mo> > </mo> <mn> 2 </mn> </math>时，p的解集是上述区间的子集, 因此p的解集可取两者中范围较大者, 即 <nobr aria-hidden="true"> [2–√+1,+∞) </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mo stretchy="false"> [ </mo> <msqrt> <mn> 2 </mn> </msqrt> <mo> + </mo> <mn> 1 </mn> <mo> , </mo> <mo> + </mo> <mi mathvariant="normal"> ∞ </mi> <mo stretchy="false"> ) </mo> </math>。
由于 <nobr aria-hidden="true"> p≥2–√+1 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> p </mi> <mo> ≥ </mo> <msqrt> <mn> 2 </mn> </msqrt> <mo> + </mo> <mn> 1 </mn> </math>, 而 <nobr aria-hidden="true"> p∈Z </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> p </mi> <mo> ∈ </mo> <mi> Z </mi> </math>, 因而 <nobr aria-hidden="true"> p≥3 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> p </mi> <mo> ≥ </mo> <mn> 3 </mn> </math>.
因此
<nobr aria-hidden="true"> a⋅b=2⋅p2=2⋅n|(n−1)! </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> a </mi> <mo> ⋅ </mo> <mi> b </mi> <mo> = </mo> <mn> 2 </mn> <mo> ⋅ </mo> <msup> <mi> p </mi> <mn> 2 </mn> </msup> <mo> = </mo> <mn> 2 </mn> <mo> ⋅ </mo> <mi> n </mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false"> | </mo> </mrow> <mo stretchy="false"> ( </mo> <mi> n </mi> <mo> − </mo> <mn> 1 </mn> <mo stretchy="false"> ) </mo> <mo> ! </mo> </math>
故 (n-1)! (mod n) = 0n是合数，且n可表示成质数p的平方，而且 p < <nobr aria-hidden="true"> 2–√+1 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msqrt> <mn> 2 </mn> </msqrt> <mo> + </mo> <mn> 1 </mn> </math>, 即 p = 2, n=4.
此时，无法找到满足条件的a和b， <nobr aria-hidden="true"> 4∤3!=6 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mn> 4 </mn> <mo> ∤ </mo> <mn> 3 </mn> <mo> ! </mo> <mo> = </mo> <mn> 6 </mn> </math>.
已AC代码：
using System;
namespace hdoj_zball
{
public class Solution
{
public int Mod(int n)
{
if (IsPrime(n))
return n - 1;
if (n == 4)
return 2;
return 0;
}
public bool IsPrime(int m)
{
if (m < 2)
return false;
for (int i = 2; i * i <= m; i++)
{
if (m % i == 0)
return false;
}
return true;
}
}
class Program
{
static void Main(string[] args)
{
int n = int.Parse(Console.ReadLine());
while (n-- > 0)
{
string[] s = Console.ReadLine().Split();
int num = int.Parse(s[0]);
Solution sol = new Solution();
Console.WriteLine(sol.Mod(num));
}
}
}
}Rank (C#):
| Exe.Time | Exe.Memory |
|---|---|
| 1185ms | 26908K |
Reference:
elementary number theory - If <nobr aria-hidden="true"> n≠4 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> n </mi> <mo> ≠ </mo> <mn> 4 </mn> </math> is composite, then <nobr aria-hidden="true"> n </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> n </mi> </math> divides <nobr aria-hidden="true"> (n−1)! </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mo stretchy="false"> ( </mo> <mi> n </mi> <mo> − </mo> <mn> 1 </mn> <mo stretchy="false"> ) </mo> <mo> ! </mo> </math>. - Mathematics Stack Exchange
https://math.stackexchange.com/questions/164852/if-n-ne-4-is-composite-then-n-divides-n-1