专栏首页大白技术控的技术自留地C#版 - HDUoj 5391 - Zball in Tina Town(素数) - 题解

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

Exe.Time

Exe.Memory

1185ms

26908K

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C#版(击败100.00%的提交) - Leetcode 372. 超级次方 - 题解

    在线提交: https://leetcode.com/problems/super-pow/

    Enjoy233
  • C#版 - ZJNUoj1259 - 幸运数字——中高级 - 题解

    Time Limit: 1000 ms       Memory Limit: 65536 KB Total Submissions: 116    Ac...

    Enjoy233
  • 桶排序(Bucket Sort)的数组实现

    桶排序Bucket Sort从1956年就开始被使用,该算法的基本思想是由E. J. Issac R. C. Singleton提出来。

    Enjoy233
  • 练习题二下

    1.1 第8题 linux 系统运行级别一般为 0-6,请分别写出每个级别的含义。 1.1.1 运行级别的含义 0 关机 1 单用户模式 2 多用户模式 没有...

    惨绿少年
  • React 性能调优——PureComponent 篇

    WEBJ2EE
  • 优化页面访问速度(四) ——前端优化

    前端的优化,主要可以通过减少HTTP请求、非实时请求改异步、缓存、文件压缩、CDN加速、独立图片服务器等。

    用户1327360
  • 《JavaScript 模式》读书笔记(2)— 基本技巧3

    无论是使用tab还是空格,只要是一致遵循的,是什么并不重要。JSLint的默认值是4个空格来缩进。那么需要对哪些内容进行缩进呢?只需要对大括号中所有的代码进行...

    zaking
  • DBA必备技能:通过truss跟踪解决监听无法启动案例

    作者简介:刘斌,云和恩墨高级技术专家,擅长数据库故障诊断分析,数据库性能优化,自动化运维开发,坚持学习、写作、分享, 在Oracle DBA的日常工作中,通过各...

    数据和云
  • Golang学习笔记 函数

    函数声明 函数使用func关键字声明,除了类型是后置的以外,剩下的地方基本和其他语言类似。特别地,和变量声明类似,如果函数参数的类型一样,同样可以只在最后添加类...

    乐百川
  • 系统性能提升利刃 | 缓存技术使用的实践与思考

    按照现在流行的互联网分层架构模型,最简单的架构当属Web响应层+DB存储层的架构。从最开始的单机混合部署Web和DB,到后来将二者拆分到不同物理机以避免共享机器...

    猿天地

扫码关注云+社区

领取腾讯云代金券