TopCoder SRM661 Div.1 250 MissingLCM 题解

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

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

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

计算\(LCM(n,m)\),我们需要把\(n\)和\(m\)都分解掉,然后得到的质数中取指数最大的,乘起来就是了。算多个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))\)

可以发现\(a\)和\(b\)就是\(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)\)就是答案

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

 

发表评论

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

*