C#版 - HDUoj 5391 - Zball in Tina Town(素数) - 题解

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 中提到威尔逊定理(n−1)!+1 (mod n)≡0⇔n(n−1)!+1 (mod n)≡0⇔n(n-1)! + 1\ (mod\ n) \equiv 0 \Leftrightarrow n is prime.

首先，来回忆一下阶乘的定义: m!=∏mk=1k=1×2×3×⋯×m.m!=∏k=1mk=1×2×3×⋯×m.m! = \prod_{k=1}^m k = 1 \times 2 \times 3 \times \dots \times m.

可得出结论: 存在a, b ∈∈\in [1, m] 使得a⋅ba⋅ba\cdot b能整除m!

假定 m=n−1m=n−1m = n-1,

原问题可分类如下:

1. n是质数，则由威尔逊定理知: (n−1)! (mod n)=−1(mod n)=n−1(n−1)! (mod n)=−1(mod n)=n−1(n-1)! \ (mod\ n) = -1 (mod\ n) = n - 1.
2. n是合数(composite)，且n不能表示为质数的平方，则∃a,b∃a,b\exists a, b使得n=a⋅b | m!n=a⋅b | m!n = a\cdot b\ |\ m!，即 a⋅b=n | (n−1)!a⋅b=n | (n−1)!a\cdot b = n\ |\ (n-1)!
3. n是合数，且n可表示成质数p的平方，而且 p > 2–√+12+1\sqrt{2}+1, 即 p≥3p≥3p\geq3 此时的目标是寻找a, b使得 a⋅b | p2a⋅b | p2a\cdot b\ |\ p^2，不妨假设 a = k1⋅pk1⋅pk_1\cdot p, b = k2⋅pk2⋅pk_2\cdot p. n=p2n=p2n = p^2, 则n的约数有1,p,p21,p,p21, p, p^2. 下面用反证法来证明为何a、b均与p线性相关，如果a(≥1≥1\geq 1)与p线性无关，则b=k⋅p2≥p2(k≥1)b=k⋅p2≥p2(k≥1)b=k\cdot p^2\geq p^2 (k\geq 1)，而b≤m=n−1=p2−1b≤m=n−1=p2−1b\leq m=n-1=p^2-1，矛盾。同理假设b与p线性无关也会出现同样的矛盾，因此a、b均与p线性相关。 1≤a=k1⋅p<b=k2⋅p≤p2−11≤a=k1⋅p<b=k2⋅p≤p2−11\leq a = k_1 \cdot p < b = k_2 \cdot p \leq p^2 - 1 让a尽量小, 则k1=1k1=1k_1=1, 令t=k2t=k2t = k_2, 于是b可表示为t⋅pt⋅pt\cdot p. ∴t⋅p≤p2−1∴t⋅p≤p2−1\therefore t\cdot p \leq p^2 -1 解上述不等式可得 p≥t+t2+4√2=f(t) (t≥2)p≥t+t2+42=f(t) (t≥2) p\geq \frac{t+\sqrt{t^2+4}}{2} = f(t) \ (t\geq 2), 容易分析得f(t)是递增函数。 当t=2t=2t = 2时, p≥2–√+1p≥2+1p \geq \sqrt{2}+1，即p∈[2–√+1,+∞)p∈[2+1,+∞)p \in [ \sqrt{2}+1, +\infty), 于是b=2⋅pb=2⋅pb=2\cdot p. 而当t>2t>2t>2时，p的解集是上述区间的子集, 因此p的解集可取两者中范围较大者, 即[2–√+1,+∞)[2+1,+∞)[ \sqrt{2}+1, +\infty)。 由于p≥2–√+1p≥2+1p \geq \sqrt{2}+1, 而 p∈Zp∈Zp\in Z, 因而p≥3p≥3p \geq 3. 因此 a⋅b=2⋅p2=2⋅n|(n−1)!a⋅b=2⋅p2=2⋅n|(n−1)! a\cdot b = 2 \cdot p^2 = 2\cdot n | (n-1)! 故 (n-1)! (mod n) = 0
4. n是合数，且n可表示成质数p的平方，而且 p < 2–√+12+1\sqrt{2}+1, 即 p = 2, n=4. 此时，无法找到满足条件的a和b，4∤3!=64∤3!=64 \nmid 3! = 6.

已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#):

Reference: elementary number theory - If n≠4n≠4n\ne 4 is composite, then nnn divides (n−1)!(n−1)!(n-1)!. - Mathematics Stack Exchange https://math.stackexchange.com/questions/164852/if-n-ne-4-is-composite-then-n-divides-n-1