首页 > 代码库 > 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; } else r = 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。