hihoCoder-week144:机会渺茫 - trash - 博客频道 - CSDN.NET
小Hi最近在追求一名学数学的女生小Z。小Z其实是想拒绝他的，但是找不到好的说辞，于是提出了这样的要求：对于给定的两个正整数N和M，小Hi随机选取一个N的约数N'，小Z随机选取一个M的约数M'，如果N'和M'相等，她就答应小Hi。
小Z让小Hi去编写这个随机程序，到时候她review过没有问题了就可以抽签了。但是小Hi写着写着，却越来越觉得机会渺茫。那么问题来了，小Hi能够追到小Z的几率是多少呢？
解决思想：
假设N有Nnum个约数，M有Mnum个约数，N和M共有same个相同的约数。对于一个公共约数，在N中抽取到它的概率为1/Nnum，M为1/Mnum,所以同时抽取到这个公共约数的概率为1/(Nnum*Mnum)。一共有same个公共约数，则总概率为same个1/(Nnum*Mnum)相加，则概率为same/(Nnum*Mnum)。
如何求解same：same即为N和M最大公因数的约数个数。
需要实现的算法：
1.给定一个数，求解它的约数总个数。
2.给定两个数，求解它们的最大公因数。
实现算法原理：
1.O(sqrt(N))求约数个数法
比如要求解36的约数，我们可以把36如下分解：
36=1*36
36=2*18
36=3*12
36=4*9
36=6*6
注意我们只写出了小于等于sqrt(36)个等式就找到了它（36）所有的约数，共九个。因为当我们找到A的约数B时，也可默认得到A/B是A的另一个约数（如果A/B和B 不相等的话），这样我们就想到，在计算N的约数个数时可以只检查前sqrt(N)个数是否为N的约数，若为，则约数个数加2（若约数的平方等于N时再-1）
具体实现代码如下
Read full article from hihoCoder-week144:机会渺茫 - trash - 博客频道 - CSDN.NET
No comments:
Post a Comment