topcoder|Topcoder SRM 661 Div1 Easy: MissingLCM topcoder|数学|数学

题目大意众所周知，LCM指最小公倍数。
令A=LCM(1~m)
B=LCM(n+1~m)
求一个最小的m使得A=B。
题解写这道题的时候，毫不犹豫，先敲了一个暴力，反正就算不能AC也可以找找规律，验证猜想。
结果发现，LCM增长得非常快，即使是n=48的小数据，也跑不出来。
于是怒而找规律，看了三组样例，以为输出就是n*2，结果就被出题人嘲讽了。出题人在某组答案并非n*2的数据后面加了一句：似乎不满足规律了。
于是我就顺着这个思路思考了下去。
我感觉，貌似如果这个数可以被拆分成两个数，也就是不是质数，就应该continue掉，然后找到最早的一个质数乘2输出。
当然这是错的，马上就WA了。
于是我有加了一句判断，就是拆分成的这两个数不能相互整除，然后就AC了。
反正我也不知道这样是不是对的，但是我知道的是：hack数据都是 2n+1 ，答案都是 2n?2 。
就这样AC了，感觉是水过的呀！！！
先贴一下我的代码，再说正解。

class MissingLCM { public: int getMin(int N) { for(int i=N; i>=1; i--){ bool f=1; for(int j=floor(sqrt(i)); j>1; j--){ if(i%j==0&&i/j!=j&&i/j%j){ f=0; break; } } if(f) return i<<1; } return 0; } };

首先可以发现的一个很明显的性质就是，答案不可能大于n*2，因为如果m取到n*2，那么对于1~n中的每个数都有它的两倍，于是一定满足A=B。正是由于这个性质，我才想到了那种奇怪的方法。
以下都是看了题解之后的心得
可以单独得看如何满足每个元素。
当然这种情况，肯定是把元素拆分成素数来看，于是我们来看每一个素数。可以发现，对于一个素数的x次幂，我们只能通过把他乘二的数来保证答案是他的倍数。于是可以先把n以内的素数不断乘自己，达到一个最大的x使得 px<=n ，于是用 px?2 更新答案。
贴一下标程吧：

vector get_primes(int N) { // Sieve of Erathostenes to find all the necessary prime numbers: vector res; vector composite(N + 1, false); for (int p = 2; p <= N; p++) { if (! composite[p]) { for (int i = p+p; i <= N; i += p) { composite[i] = true; } res.push_back(p); } } return res; }int get_exponent(int x, int p) { int r = 0; while (x % p == 0) { r++; x /= p; } return r; }int getMin(int N) { int res = 2; // For each prime number <= N: // 找到<=n的每个质数 for (int p: get_primes(N) ) { // first find the maximum exponent of pamong numbers <= N // 找到p<=n的最大的幂 int max_exp = 0; int i = p; while (i <= N) { max_exp = std::max(max_exp, get_exponent(i,p) ); i += p; } // seek the minimum i such that get_exponent(i,p) >= max_exp: // 找到最小的i使得get_exponent(i,p)>=max_exp while (get_exponent(i,p) < max_exp) { i += p; } // the maximum for all ps is the result: // 最大的ps是答案。 res = std::max(res, i); } return res; }

【topcoder|Topcoder SRM 661 Div1 Easy: MissingLCM】顺便说一句题外话，我居然在topcoder上看见一个代码为空的人AC了，于是我随便交了一组数据上去，居然Challenge Successful了！什么情况？