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)\)就是答案

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

vector<int> sieve(int n) {
	int s = sqrt((double)n);
	vector<int> ans;
	vector<bool> vis(n + 1, false);
	for(int i = 2; i <= s; ++i) if(!vis[i])
		for(int j = i * i; j <= n; j += i) vis[j] = true;
	for(int i = 2; i <= n; ++i) if(!vis[i])
		ans.push_back(i);
	return ans;
}
int get_exp(int x, int p) {
	int ans = 0;
	while(x % p == 0) ++ans, x /= p;
	return ans;
}
class MissingLCM {
	public:
	int getMin(int n) {
		vector<int> prime = sieve(n);
		int ans = 2;
		for(vector<int>::iterator p = prime.begin(); p != prime.end(); ++p) {
			int max_exp = 0, i = *p;
			while(i <= n) max_exp = max(max_exp, get_exp(i, *p)), i += *p;
			while(get_exp(i, *p) < max_exp) i += *p;
			ans = max(ans, i);
		}
		return ans;
	}
};

 

发表评论

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