Light 1289 LCM from 1 to n 素数筛选位优化

素数筛选位优化"/>

Light 1289 LCM from 1 to n 素数筛选位优化

题目来源：Light 1289 LCM from 1 to n

题意：。。

思路：从1到n 打过某个数是以一个素数的几次方 那么答案就乘以这个素数

主要是筛选素数 存不下 位优化 一个整数32位标记32个数 内存缩小32倍

是学习别人的

#include <cstdio>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxn = 100000010;
const int maxm = 6000000;
unsigned int dp[maxm];
int prime[maxm];
int vis[maxn/32+10];
//筛素数 
int sieve()
{//memset(vis, 0, sizeof(vis));//vis[0] = vis[1] = 1;prime[0] = 2;dp[0] = 2;int c = 0;for(int i = 3; i < maxn; i += 2){if(!(vis[i/32]&(1<<(i%32)))){prime[++c] = i;dp[c] = dp[c-1] * i;for(int j = i*2; j < maxn; j += i)vis[j/32] |= (1<<(j%32));}}return c;
}int main()
{int c = sieve();int cas = 1;int T;scanf("%d", &T);while(T--){int n;scanf("%d", &n);int l = 0, r = c-1, m;while(l <= r){int mid = (l + r) >> 1;if(prime[mid] <= n){m = mid;l = mid + 1;}elser = mid - 1;}//printf("%d\n", m);unsigned int ans = dp[m];for(int i = 0; i <= m && prime[i]*prime[i] <= n; i++){int x = prime[i];int y = prime[i]*prime[i];while(y <= n && y / x == prime[i]){//printf("**%d", y);ans *= prime[i];x *= prime[i];y *= prime[i];}//ans *= x;}printf("Case %d: %u\n", cas++, ans);}return 0;
}