分解质因数

求卡特兰数 (其实就是组合数)
大组合数且模数非素数，无法求逆元
高精组合数，如果你不想打高精除的话（没人想打）

方法：

1

以求高精组合数为例

一般地，对于$n m leq 10^6$ 可以打素数表，然后在mark i*prime[j]时附上标记prime[j] 其实就是i*prime[j] 的最小质因数，这样可以在分解时将复杂度控制在$O(logn)$以下。

 1 void get_prime()
 2 {
 3     F(i,2,n)
 4     {
 5         if(!mark[i])
 6         {
 7             prime[++pc]=i;
 8             mark[i]=i;
 9         }
10         F(j,1,pc)
11         {
12             if(i*prime[j]>n) break;
13             mark[i*prime[j]]=prime[j];
14             if(i%prime[j]==0) break;
15         }
16     }
17 }

线性筛素数并标记

1 while(x!=1)
2 {
3     ++pz[mark[x]];
4     x/=mark[x];
5 }

对x分解质因数

同理对分母分解，然后我们只要--pz[]就可以了（组合数是整数，所以我们可以预见分母会被约掉）。

1 F(i,2,n) while(pz[i]--) dcheng(a,i);

高精乘低精

实际上pz[]有很多下标是无用的，我们可以让mark[]存素数的标号（即在prime[]中的下标）。这样在n m很大时可以减少上面代码的循环次数。

2

以下不是求组合数而单论分解。设x为要分解的数

对于x很大(1e9)，我们可以用试除法。

枚举$1~sqrt{x}$ 对于一个枚举到的i，除到不能整除为止，记录因数，显然这样得到的因数都是素数。

枚举完后，若x!=1 则将x加入质因子中。

这样做的正确性：反证法：假设有两个>sqrt(x)的质因数，那么将它们相乘会>x，与命题矛盾，得证。

然后我们就可以在$O(sqrt{x})$下没有多开一个数组而愉快地解决了问题。

总结

两种算法比较：

1.对于要频繁分解质因数的情况，第一种更优。只要$O(n)$线性筛一遍，然后单次分解$O(logn)$。所以当估计操作数达到$O(sqrt(n))$直接第一种

2.对于x很大，或分解次数很少的情况，第二种更优。