51nod-1434 区间LCM
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
题目来源： TopCoder
基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题
收藏
关注
例如，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值。
Input
多组测试数据，第一行一个整数T，表示测试数据数量，1<=T<=5每组测试数据有相同的结构构成：每组数据一行一个整数N,1<=N<=1000000。
Output
每组数据一行输出，即M的最小值。
Input示例
3123
Output示例
246
只要1到n中每个质因子的指数最高次，在n+1, m中也出现即可
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define maxn 1000000
using namespace std;
typedef long long ll;
int cnt;
int prime[maxn+5], p[maxn+5];
void Prime(){
for(int i = 2; i <= maxn; i++){
if(prime[i] == 0){
p[cnt++] = i;
for(ll j = (ll)i * i; j <= maxn; j += i){
prime[j] = 1;
}
}
}
}
int main(){
// freopen("in.txt", "r", stdin);
int t;
Prime();
scanf("%d", &t);
while(t--){
ll n;
scanf("%I64d", &n);
int ans = 2;
for(int i = 0; i < cnt && p[i] <= n; i++){
ll sum = 1;
while(sum * p[i] <= n)
sum *= p[i];
ans = max((ll)ans, (n / sum + 1) * sum);
}
printf("%d\n", ans);
}
return 0;
}
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |