玩玩算法 菜死了 大概记录一下我的弃坑过程吧((
题目
思路
先分析用例
10 => 2*5
20 => 2*2*5
结果 2
3 => 3
60 => 2*2*3*5
结果 4
各种看规律 没看出来 直到我出去吃饭的时候查维基百科看到张图
用画图来解决问题! 把最大公因数和最小公倍数拆开来, 再画到一个韦恩图里:
// 当时的原草稿 字有点丑嘿嘿嘿
对于 10 和 20 的用例来说, 由于要组成的数的最大公因数是 10, 所以它们里面必须得有 2 和 5, 而韦恩图外圈的 2 不可能俩数都有, 不然这个 2 就变到中间去了, 于是有 [10 20] [20 10] 两种组合
对于另一个用例, 最大公因数是3, 而 2 2 5.. 这两个 2 必须得放到两个数之一里, 不然就拆不出这种结果, 而如果两个2分居两个数体内, 就会造成上面跑到韦恩图中间的结果..
于是就变成了一个组合数的问题
由于最小公倍数一定包含最大公因数(为啥?)
- 如果最小公倍数不能整除最大公因数 返回0 (这玩意是我 Wrong Answer 发现的)
- 用最小公倍数除掉最大公因数, 就没韦恩图中间部分了, 此时求剩余的因数有多少种 (2 2 3 有两种) 再用 (2^种数) (排列组合) 就得到了结果.
不保证思路的正确性
貌似有更好解法 此处仅为我的想法
怎么求因数有多少种
我把题目数据以内的质数全列出来了然后硬算 x % prime == 0