search

chufengt / aoapc-book

Automatically exported from code.google.com/p/aoapc-book
0 stars 0 forks source link

入门经典（第2版）例题10-29魔法GCD(UVa1642)里面的一句求解 #41

Open GoogleCodeExporter opened 9 years ago

GoogleCodeExporter commented 9 years ago 
“换句话说，不同的gcd值最多只有log_2 j种”
请问这个结论是如何得到的？

Original issue reported on code.google.com by YHYl...@gmail.com on 16 Aug 2014 at 10:44

GoogleCodeExporter commented 9 years ago 
想了一想，终于明白了，来回答一下。
最小的素数为2.因此在最坏情况下x=\prod_{i=1}^n 
p_i^{a_i}中，\sum_{i=1}^n a_i=log_2 j.
以上\prod和\sum分别代表连乘和连加号。

Original comment by YHYl...@gmail.com on 17 Aug 2014 at 1:04