51Nod 1434 区间LCM

Problem

一个整数序列S的LCM（最小公倍数）是指最小的正整数X使得它是序列S中所有元素的倍数，那么LCM(S)=X。

例如，LCM(2)=2,LCM(4,6)=12,LCM(1,2,3,4,5)=60。

现在给定一个整数N（1<=N<=1000000）,需要找到一个整数M，满足M>N，同时LCM(1,2,3,4,...,N-1,N) 整除 LCM(N+1,N+2,....,M-1,M)，即LCM(N+1,N+2,....,M-1,M)是LCM(1,2,3,4,...,N-1,N) 的倍数.求最小的M值。

Solution

提供几种等价的做法。

官方：保证[1,N]区间每个质数的指数最大值在[N+1,M]间至少出现一次。

题解1：2*n必然满足条件，且如果n和LCM(1,2,3,...n-1)的gcd=n，则LCM(1,2,3,...,n-1)=LCM(1,2,3,...,n-1,n)，那么n--，找到最小的n即可。发现n和LCM(1,2,3,...n-1)的gcd=n在n不是单个质数幂次时成立，就从n一路质因数分解下来。

我的做法：对小于等于n的每个质数查找幂次，找到最大的*2即可。

我参考的做法：对小于n的每个质数q： 计算最高次幂r, q^r < n 计算最大倍数k， k* q^r < n ret = max(ret, (k+1)* q^r)

思路从这里来的，不过没明白这位老哥的做法，猜测一下，如果k>1必然会存在qr<st<n，所以求出来的k必然等于1，就是我这个做法。

Code

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=1e6; 
bool ipr[MAXN+20];
int cnt,pri[MAXN/5];
void prime(){//埃式筛法 
	int N=sqrt(MAXN)+0.5,mul;
	memset(ipr,true,sizeof(ipr));
	ipr[1]=false;	
	for(int i=2;i<=N;i++){
		if(ipr[i]==true){
			i==2?mul=1:mul=2;
			for(int j=i*i;j<=MAXN;j+=i*mul){
				ipr[j]=false;
			}
		}
	}
	for(int i=2;i<=MAXN;i++){
		if(ipr[i]==true){
			pri[++cnt]=i;
		}
	}
}
int T,n;
ll solve(int n){
	ll ans=0;
	for(int i=1;i<=cnt;i++){
		ll cur=1;
		for(int j=1;cur<=n;j++){
			cur*=pri[i];
		}
		cur/=pri[i];
		ans=max(ans,cur);
	}
	return ans*2;
}
int main(){
	prime();
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		printf("%lld\n",solve(n));
	}
	return 0;
}