牛客寒假集训J题一群小青蛙呱蹦呱蹦呱
题目链接
求n个数的LCM。
由唯一分解定理得:
$$a=p_1^{k_1}\times p_2^{k_2}\times p_3^{k_3}\times …\times p_m^{k_m}$$
$$b=p_1^{j_1}\times p_2^{j_2}\times p_3^{j_3}\times …\times p_m^{j_m}$$
其中p为质数。
有
$$gcd(a,b)=p_1^{min(k_1,j_1)}\times p_2^{min(k_2,j_2)}\times p_3^{min(k_3,j_3)}\times …\times p_m^{min(k_m,j_m)}$$
$$lcm(a,b)=p_1^{max(k_1,j_1)}\times p_2^{max(k_2,j_2)}\times p_3^{max(k_3,j_3)}\times …\times p_m^{max(k_m,j_m)}$$
上面的性质可以由2个推广到n个。
题解
这题显然是要求所有n以内,包含两个及以上不同质因子的数
的LCM。
根据上述性质,要求LCM,我们只需求出所有p的max值即可,显然,和2组合时,每个p可以取到max。
因此我们可以用欧拉筛筛出所有素数,然后对于每个素数,看能用2和最多几个该素数相乘得到。
2本身比较特殊,因为题目要求必须两个不同的质因子,所以计算2的贡献时,我们选用第二小的3即可。
还有一个小细节:
欧拉筛筛素数的时候,只需筛到n/2,因为(n/2,n]的素数肯定不可能和另一个素数(最小为2)相乘能得到n。
代码
1 | /* |