• 周四. 4月 25th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

分解质因数

admin

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

方法:

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

《分解质因数》有2个想法
  1. How to track the location of the other person’s phone without their knowledge? You will be able to track and monitor text messages, phone calls, location history and much more. Free Remote Tracking and Recording of Husband’s Phone Cell Phone Spy. Best Apps to Download for Free to Spy on Another Phone.

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注