分解质因数 - OI Wiki

[Xeonacid]

https://oi-wiki.org/math/pollard-rho/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[ghost]

前面说"一个房间中至少 23 人，使其中两个人生日相同的概率达到 50%"
后面说"那么在一年有 n 天的情况下，当房间中有 根号n 个人时，至少有两个人的生日相同。"
我想当 n = 365 时 根号n = 19.10 < 23，一个房间有 23 人时概率都只有 50%，为什么 19.10 人就能接近 100% 呢？
前后矛盾了吧

[ghost]

给在这卡壳的人提个醒：

for (goal = 1;; goal <<= 1, s = t, val = 1) 中间是没有退出条件的。

因为 if (d > 1) return d; 在 $s = t$ 时返回 x。

[TBB000623]

@null 前面说"一个房间中至少 23 人，使其中两个人生日相同的概率达到 50%"
后面说"那么在一年有 n 天的情况下，当房间中有 根号n 个人时，至少有两个人的生日相同。"
我想当 n = 365 时 根号n = 19.10 < 23，一个房间有 23 人时概率都只有 50%，为什么 19.10 人就能接近 100% 呢？
前后矛盾了吧

这里这个不是准确的Sqrt(n)，这个数大概在1.2*Sqrt(n)以下