首页 > 代码库 > 51nod 1434 区间LCM 素数

51nod 1434 区间LCM 素数

2024-08-14 00:20:55   218人阅读

1434 区间LCM
题目来源： TopCoder
基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题
 
一个整数序列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值。
Input
多组测试数据，第一行一个整数T，表示测试数据数量，1<=T<=5每组测试数据有相同的结构构成：每组数据一行一个整数N,1<=N<=1000000。
Output
每组数据一行输出，即M的最小值。
Input示例
3123
Output示例
246

思路:对于【1，N】区间的素数， 设为p1, p2, p3, ~，pn
找到最小的c1和k1 使得 m >= c1*p1^k1 > n;
result = max{c1*p1^k1, c2*p2^k2,~，cn*pn^kn};
 1 #include <iostream> 2 #include <cstdio> 3  4 using namespace std; 5 const int MAXN = 1e6; 6 int prime[MAXN+10], num; 7 bool a[MAXN+10]; 8  9 void init(){10     num = 0;11     a[1] = false;12     for(int i = 2; i <= MAXN; i++) a[i] = true;13     for(int i = 2; i <= MAXN; i++){14         if(a[i]){15             prime[++num] = i;16         }17         for(int j = 1; j <= num; j++){18             if(i*prime[j] > MAXN) break;19             a[i*prime[j]] = false;20             if(i%prime[j] == 0) break;21         }22     }23 }24 int slove(int n){25     int res = 2;26         for(int i = 1; prime[i] <= n && i <= num; i++){27                 int sum = prime[i];28                 while(sum <= n/prime[i]) sum *= prime[i];29                 res= max(res, (n/sum + 1)*sum);30         }31     return res;32 }33 int main(){34     int T, n;35     init();36     scanf("%d", &T);37     while(T--){38         scanf("%d", &n);39         printf("%d\n", slove(n));40     }41     return 0;42 }

 


51nod 1434 区间LCM 素数


联系
我们