51NOD 1434 区间LCM(素数筛)

传送门

1434 区间LCM
题目来源: TopCoder
基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题 收藏 关注
1个整数序列S的LCM(最小公倍数)是指最小的正整数X使得它是序列S中所有元素的倍数,那末LCM(S)=X。
例如,LCM(2)=2,LCM(4,6)=12,LCM(1,2,3,4,5)=60。
现在给定1个整数N(1<=N<=1000000),需要找到1个整数M,满足M>N,同时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) 的倍数.求最小的M值。
Input
多组测试数据,第1行1个整数T,表示测试数据数量,1<=T<=5
每组测试数据有相同的结构构成:
每组数据1行1个整数N,1<=N<=1000000。
Output
每组数据1行输出,即M的最小值。
Input示例
3
1
2
3
Output示例
2
4
6
解题思路:

假定有质数K,可以求出t,使得K的t次方恰好小于等于m(K^t<=m)那末lcm(1,2,…,m)分解质因数中1定而且最多有t个质数K连乘,其实我们可以就是求的质数的最高次幂,这样就能够很快地吧lcm(1,2,…,m)分解质因数那末怎样把 lcm(n+1,n+2,…,m)分解质因数呢依然假定质数K,可以求出最大的t,和1个常数c(1<=c < K),使得 n+1<=c*K^t<=m
那末lcm(n+1,n+2,…,m)分解质因数中1定而且最多有t个质数K连乘。比如说质数3,n=16,m=22,可以求的c=2,t=2,即17<=2*3^2=18<=22,这样lcm(17,18,19,20,21,22)中最多有2个质数3连乘既然知道怎样求lcm(n+1,n+2,..,m)和lcm(1,2,..,m)了来探讨1下怎样求最小的m吧我们想让这两个lcm分解质因数后完全1样,也就是说连乘的质数个数也完全相等。也就是说,对每一个质数K都可以满足,存在c和最大的t 使得n+1<=c*K^t<=m对大于n小于m的质数,我们假定是P,那末1定n+1<=P<=m,1定可以满足条件所以我们就只看小于等于n的质数就能够了由于要使每一个小于N的质数K,都存在c和最大的t 使得n+1<=c*K^t<=m,我们枚举每个质数,并求得c和t,使得恰好c*K^t>=n,
答案就取最大的c*K^t,即 max( c*K^t )这样lcm(1,2,…,m)和lcm(n+1,n+2,…,m)的分解质因数后均最少有t个质数K。如果终究m有 k^(t+1)<=m,那末这个K^(t+1)>n1定成立,故仍满足条件
代码:

#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])///素数
{
int sum = i;
while(sum <= n/i)
sum *= i;
ans = max(ans, (n/sum+1)*sum);
}
}
cout<<ans<<endl;
}
return 0;
}
波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 51NOD 1434 区间LCM(素数筛)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡