05-09 23:06 已编辑山东大学 C++ 发布于北京

关注

关于F唯一性的另一种证明方式

奇素数回路

https://ac.nowcoder.com/acm/contest/109081/F

证明：若 $gcd(p, n) = 1$ ， $k_1, k_2 \in \{0, 1, \dots, n-1\}$ ，序列 $a_k = (k * p \mod n)+1$ 包含 n 个从 1 到 n 的不同整数，

等效于：若p与n互质，则在 $k \in \{0, 1, \dots, n-1\}$ 时， $k$ 不同时 $k \cdot p \mod n$ 的值也不同。

我们可以使用反证法+裴署定理证明

因为 $\gcd(p, n) = 1$ ，所以存在整数 $x$ 和 $y$ 使得 $x \cdot p + y \cdot n = 1$ （裴署定理）。

显然，两边模 $n$ ，知 $x \cdot p \equiv 1 \pmod{n}$ ，即 $x$ 是 $p$ 的乘法逆元。

这里使用反证法：

如果 $k_1 \neq k_2$ 且 $k_1 \cdot p \equiv k_2 \cdot p \pmod{n}$ ，我们可以两边乘以 $x$ （ $p$ 的逆元）：

x \cdot k_1 \cdot p \equiv x \cdot k_2 \cdot p \pmod{n} \\ \Rightarrow k_1 \cdot (x \cdot p) \equiv k_2 \cdot (x \cdot p) \pmod{n} \\ \Rightarrow k_1 \cdot 1 \equiv k_2 \cdot 1 \pmod{n} \\ \Rightarrow k_1 \equiv k_2 \pmod{n}.

因为 $k_1, k_2 \in \{0, 1, \dots, n-1\}$ ，所以 $k_1 = k_2$ ，矛盾。

故得证。

全部评论

推荐最新楼层

不愿透露姓名的神秘牛友

08-07 14:33

我嘞个速度与激情😯

锐石创芯，宣讲3小时以后直接面试，吓死鼠鼠了

点赞评论收藏

08-12 16:53

中南大学 Java

英伟达想招谁？

打开英伟达笔试一看，看傻了，两个小时六道编程大题，什么样的人才能做完这种笔试题。。。

Linux内核学习记...：你这个问题等同于问清北招谁

投递英伟达等公司10个岗位

点赞评论收藏

06-17 00:26

门头沟学院 Java

求助！！！

前途渺茫啊。自学Java少说已经有半年多了。目前某软件机会都是已读不回，个别投投简历也是没有后续。这个节骨眼这样也挺正常的。但是三本学历怕是秋招没有啥竞争力，甚至怀疑自己适不适合开发（想转测开去了），已经差不多一个月没写代码了，一直在背八股。继续沉淀还是转行测开？友友们

程序员小白条：建议换下项目，智能 AI 旅游推荐平台：https://github.com/luoye6/vue3_tourism_frontend 智能 AI 校园二手交易平台：https://github.com/luoye6/vue3_trade_frontend GPT 智能图书馆：https://github.com/luoye6/Vue_BookManageSystem 选项目要选自己能掌握的，然后最好能自己拓展的，分布式这种尽量别去写，不然你只能背八股文了，另外实习的话要多投，尤其是学历不利的情况下，多找几段实习，最好公司title大一点的

无实习如何秋招上岸

点赞评论收藏

07-31 17:07

湘潭大学嵌入式工程师

嵌入式烂完了？

不！是我烂完了！！嵌入式怎么这么难找实习？？要摆烂了，开学就大四秋招了，真的找不到实习，有没有大佬帮我看看这份简历有没有问题，有没有什么需要修改的地方。感觉自己大学算是什么都没学，也没有什么竞赛经历，项目也是临时做出来的有一些地方是编的，找不到实习是不是秋招就毁完了，焦虑啊😭😭

DKS233：项目写太简单了，你用什么技术实现了什么功能，优化了多少，分了哪些模块，解决了哪些难点，最好分模块写，你写的太模糊了。精通还是少用吧，你确定问你底层你扛的住吗，最好用熟悉。具备良好**意识，这种空话不要写，技能层面，要写就写实在的，比如“熟悉常用数据结构，如，堆，栈，链表，哈希表，平衡树”这种

你的简历改到第几版了

点赞评论收藏