題目：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=26999

題意：給定一個正整數n，求的值，輸入數據有10000組，每組一個數n，1<=n<=10^8。

分析：定義為1,2,3,...,n的最小公倍數。則可以發現有如下結論：

所以有：

那么，我們先把所有素數的連乘預處理出來，然后再對每一個素數的整數次冪根據n的不同進行操作。在素數篩選中，我們利用位圖來節省內存空間。

#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> #include <math.h>using namespace std; typedef unsigned int uint; const int N = 100000005; const int M = 6000005; const int SHIFT = 5; const int RADIX = (1 << SHIFT) - 1;int flag[(N>>SHIFT)+1]; uint sum[M]; int p[M]; int k;inline void SetBit(int x) {flag[x>>SHIFT] |= (1<<(x&RADIX)); }inline bool GetBit(int x) {return flag[x>>SHIFT] & (1<<(x&RADIX)); }void isprime() {k = 0;for(int i=2; i<N; i++){if(!GetBit(i)){p[k++] = i;for(int j=i+i; j<N; j+=i)SetBit(j);}} }void Init() {sum[0] = p[0];for(int i=1; i<k; i++)sum[i] = sum[i-1] * p[i]; }int main() {isprime();Init();int T,n,tt = 1;scanf("%d",&T);while(T--){scanf("%d",&n);printf("Case %d: ",tt++);uint ans = 1;int cnt = 1;while(1){int m = (int)pow(n+0.9,1.0/cnt);if(m < 2) break;int i = lower_bound(p,p+k,m) - p;if(p[i] != m) i--;ans *= sum[i];cnt++;}printf("%u\n",ans);}return 0; }

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的LCM from 1 to n的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。