·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接:http://poj.org/problem?id=1365
这题是质因数分解,首先生成一个素数表,然后通过这个表来找出x-1的每个质因数以及质因数的次数。需要注意的一点是不同于一般的筛法,这个生成素数表的算法要枚举出范围内所有的素数,因而第一层循环不能只循环到sqrt(r),而必须需要循环到r。另外在对x-1做质因数分解的时候不要忽略x-1是大质数的情况。
1 |
|