LibieOJ 6165 一道水题 (线性筛)
2024-08-30 13:38:30
题目链接 LOJ6165
题目意思其实就是求LCM(1, 2, 3, ..., n)
直接用线性筛求出1到1e8之间的所有质数
然后对于每个质数p,他对答案的贡献为$p^{i}$ 其中$p^{i}$小于等于n且要最大。
c数组可能很大,所以我开了bitset...
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i) typedef long long LL; const int N = 6170736;
const int M = 100000002;
const LL mod = 100000007; int n, pn;
int p[N];
bitset <M> c;
LL ans = 1LL;
int v; int main(){ scanf("%d", &n);
pn = 0;
rep(i, 2, n){
if (!c[i]){
p[++pn] = i;
for (LL s = i; s <= n; s *= i)
ans = ans * i % mod;
} rep(j, 1, pn){
v = i * p[j];
if (v > n) break;
c[v] = 1;
if (i % p[j] == 0) break;
}
}
printf("%lld\n", ans);
return 0;
}
最新文章
- angular-ui分页组件
- 笔记26-徐 SQLSERVER内存分配和常见内存问题
- W3cshool之JavaScript基础
- 块级&;行内(内联)元素
- HTML5 localStorage and sessionStorage
- ArcPy 函数列表(按字母顺序)
- 部分 CM11 系统 Android 平板执行植物大战僵尸 2 黑屏的解决的方法
- iOS 开发中的争议(二)
- Android Camera开发:使用TextureView和SurfaceTexture预览Camera 基础拍照demo
- 怎样在thinkphp里面执行原生的sql语句
- JDK自带的日志Logging
- ●BZOJ 1854 [Scoi2010]游戏
- Java集合学习总结
- 【esri-loader】帮助文档翻译 part1 是什么,怎么安装,为什么要用它
- Luogu 3371【模板】单源最短路径
- App遍历探讨(含源代码)
- 设计模式之适配器模式(Adapter)(6)
- CF912E Prime Gift
- mysql 定时备份任务
- 关于Dos命令中存在中文的解决方法