Smart Yanzi
Description
给你一个数 S ,求有多少数的约数和等于 S 。
Solution
对于一个数 S ,根据算数基本定理,有分解式:
S=pa11pa22pa33…pann所以约数和就是
sum=n∏i=1ai∑j=0pji由于 S<=2∗109 ,考虑枚举 S 的所有因子,先筛出 √S 以内的质数,然后枚举 pi ,对于每个 pi 枚举 ai ,爆搜,如果将 S 分解成功,答案 +1 。
同时,如果 S−1 是一个质数,且 >= 当前搜的 pi ,答案也要 +1 ,因为 S−1 也是此时构造出的数的因子。
其实我们是先把质因子全部取出来,然后找所有的乘起来的可能,对于每种可能都枚举它是否成立。
就是把 S 拆掉,然后再拼回去。
Code:
1 |
|