傳送門(mén)
1434 區(qū)間LCM
題目來(lái)源： TopCoder
基準(zhǔn)時(shí)間限制：1 秒 空間限制：131072 KB 分值: 40 難度：4級(jí)算法題 收藏 關(guān)注
1個(gè)整數(shù)序列S的LCM（最小公倍數(shù)）是指最小的正整數(shù)X使得它是序列S中所有元素的倍數(shù)，那末LCM(S)=X。
例如，LCM(2)=2,LCM(4,6)=12,LCM(1,2,3,4,5)=60。
現(xiàn)在給定1個(gè)整數(shù)N（1<=N<=1000000）,需要找到1個(gè)整數(shù)M，滿(mǎn)足M>N，同時(shí)LCM(1,2,3,4,…,N⑴,N) 整除 LCM(N+1,N+2,….,M⑴,M)，即LCM(N+1,N+2,….,M⑴,M)是LCM(1,2,3,4,…,N⑴,N) 的倍數(shù).求最小的M值。
Input
多組測(cè)試數(shù)據(jù)，第1行1個(gè)整數(shù)T，表示測(cè)試數(shù)據(jù)數(shù)量，1<=T<=5
每組測(cè)試數(shù)據(jù)有相同的結(jié)構(gòu)構(gòu)成：
每組數(shù)據(jù)1行1個(gè)整數(shù)N,1<=N<=1000000。
Output
每組數(shù)據(jù)1行輸出，即M的最小值。
Input示例
3
1
2
3
Output示例
2
4
6
解題思路：
假定有質(zhì)數(shù)K，可以求出t，使得K的t次方恰好小于等于m（K^t<=m）那末lcm(1,2,…,m)分解質(zhì)因數(shù)中1定而且最多有t個(gè)質(zhì)數(shù)K連乘，其實(shí)我們可以就是求的質(zhì)數(shù)的最高次冪，這樣就能夠很快地吧lcm(1,2,…,m)分解質(zhì)因數(shù)那末怎樣把 lcm(n+1,n+2,…,m)分解質(zhì)因數(shù)呢依然假定質(zhì)數(shù)K，可以求出最大的t，和1個(gè)常數(shù)c（1<=c < K)，使得 n+1<=c*K^t<=m
那末lcm(n+1,n+2,…,m)分解質(zhì)因數(shù)中1定而且最多有t個(gè)質(zhì)數(shù)K連乘。比如說(shuō)質(zhì)數(shù)3，n=16,m=22,可以求的c=2,t=2，即17<=2*3^2=18<=22，這樣lcm(17,18,19,20,21,22)中最多有2個(gè)質(zhì)數(shù)3連乘既然知道怎樣求lcm(n+1,n+2,..,m)和lcm(1,2,..,m)了來(lái)探討1下怎樣求最小的m吧我們想讓這兩個(gè)lcm分解質(zhì)因數(shù)后完全1樣，也就是說(shuō)連乘的質(zhì)數(shù)個(gè)數(shù)也完全相等。也就是說(shuō)，對(duì)每一個(gè)質(zhì)數(shù)K都可以滿(mǎn)足，存在c和最大的t 使得n+1<=c*K^t<=m對(duì)大于n小于m的質(zhì)數(shù)，我們假定是P，那末1定n+1<=P<=m，1定可以滿(mǎn)足條件所以我們就只看小于等于n的質(zhì)數(shù)就能夠了由于要使每一個(gè)小于N的質(zhì)數(shù)K，都存在c和最大的t 使得n+1<=c*K^t<=m，我們枚舉每個(gè)質(zhì)數(shù)，并求得c和t，使得恰好c*K^t>=n，
答案就取最大的c*K^t，即 max( c*K^t )這樣lcm(1,2,…,m)和lcm(n+1,n+2,…,m)的分解質(zhì)因數(shù)后均最少有t個(gè)質(zhì)數(shù)K。如果終究m有 k^(t+1)<=m，那末這個(gè)K^(t+1)>n1定成立，故仍滿(mǎn)足條件
代碼：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 1e6+5;
LL p[MAXN];
bool prime[MAXN];
int k;
void isprime()
{
k = 0;
memset(prime, 0, sizeof(prime));
prime[0] = prime[1] = 1;
for(LL i=2; i<MAXN; i++)
{
if(!prime[i])
{
p[k++] = i;
for(LL j=i*i; j<MAXN; j+=i)
prime[j] = 1;
}
}
}
int main()
{
isprime();
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
int ans = 2;
for(int i=2; i<=n; i++)
{
if(!prime[i])///素?cái)?shù)
{
int sum = i;
while(sum <= n/i)
sum *= i;
ans = max(ans, (n/sum+1)*sum);
}
}
cout<<ans<<endl;
}
return 0;
}
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊(cè)，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請(qǐng)聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
