TopCoder SRM661 Div.1 250 MissingLCM 题解

题目大意:给出一个整数n(n\le 1000000),求一个整数m (m data-recalc-dims=n)" />,使得LCM(1,2,3,\dots,m)=LCM(n+1,n+2,n+3,\dots,m)

Div1 的250都不会做看了官方题解T T没救了

首先考虑一下LCM是怎么计算的。

计算LCM(n,m),我们需要把nm都分解掉,然后得到的质数中取指数最大的,乘起来就是了。算多个LCM也是一样。

所以对于一个质数p,我们定义e_p(n)=max(t),p^t|n

然后考虑每一个质数p

定义a=max(e_p(n+1),e_p(n+2),\dots,e_p(m))\\b=max(e_p(1),e_p(2),\dots,e_p(m))

可以发现ab就是LCM(n+1,n+2,n+3,\dots,m)LCM(1,2,3,\dots,m)中p的指数

要求a=b

再定义c=max(e_p(1),e_p(2),\dots,e_p(n)),那么可以发现b=max(c,a),而c根据给定的n是已经确定的,且我们要求a=b,则a\ge c

因此我们枚举p,将p对应的c算出来,再从小到大枚举p的倍数i,把i当做m满足上述要求(a\ge c)时停止。max(i)就是答案

不要问我题解为什么和官方题解这么像。。也不要问我为什么代码和官方代码那么像。。

 

发表评论

电子邮件地址不会被公开。

*