• 分解质因数


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

    方法:

    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很大,或分解次数很少的情况,第二种更优。

  • 相关阅读:
    org.apache.hadoop.ipc.RemoteException(org.apache.hadoop.security.AccessControlException)
    linux命令之find和locate
    Java多线程3:Thread中的静态方法
    session的使用
    cookie的简单使用
    Spring 注入集合类型
    对Spring 容器管理事务支持的总结
    对SpringDAO层支持的总结
    为spring代理类设置属性值
    在spring中获取代理对象代理的目标对象工具类
  • 原文地址:https://www.cnblogs.com/hzoi-yzh/p/11223690.html
一二三 - 开发者的网上家园