51NOD 1434 区间LCM（素数筛）

发布时间：2020-12-13 21:09:21 所属栏目：PHP教程来源：网络整理

导读：传送门 1434 区间LCM 题目来源： TopCoder 基准时间限制：1 秒空间限制：131072 KB 分值: 40 难度：4级算法题收藏关注 1个整数序列S的LCM（最小公倍数）是指最小的正整数X使得它是序列S中所有元素的倍数，那末LCM(S)=X。例如，LCM(2)=2,LCM(4,6)=12,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,…,N⑴,N) 整除 LCM(N+1,N+2,….,M⑴,M)，即LCM(N+1,M)是LCM(1,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,m)分解质因数中1定而且最多有t个质数K连乘，其实我们可以就是求的质数的最高次幂，这样就能够很快地吧lcm(1,m)分解质因数那末怎样把 lcm(n+1,n+2,m)分解质因数呢依然假定质数K，可以求出最大的t，和1个常数c（1<=c < K)，使得 n+1<=c*K^t<=m
那末lcm(n+1,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,..,m)和lcm(1,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,m)和lcm(n+1,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;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!