题目链接 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;
}

最新文章

  1. angular-ui分页组件
  2. 笔记26-徐 SQLSERVER内存分配和常见内存问题
  3. W3cshool之JavaScript基础
  4. 块级&amp;行内(内联)元素
  5. HTML5 localStorage and sessionStorage
  6. ArcPy 函数列表(按字母顺序)
  7. 部分 CM11 系统 Android 平板执行植物大战僵尸 2 黑屏的解决的方法
  8. iOS 开发中的争议(二)
  9. Android Camera开发:使用TextureView和SurfaceTexture预览Camera 基础拍照demo
  10. 怎样在thinkphp里面执行原生的sql语句
  11. JDK自带的日志Logging
  12. ●BZOJ 1854 [Scoi2010]游戏
  13. Java集合学习总结
  14. 【esri-loader】帮助文档翻译 part1 是什么,怎么安装,为什么要用它
  15. Luogu 3371【模板】单源最短路径
  16. App遍历探讨(含源代码)
  17. 设计模式之适配器模式(Adapter)(6)
  18. CF912E Prime Gift
  19. mysql 定时备份任务
  20. 关于Dos命令中存在中文的解决方法

热门文章

  1. C03 程序逻辑
  2. QT5:第八章 信号与槽机制
  3. SpringBoot整合Thymeleaf
  4. iptables 过滤字符串
  5. C++模板 &#183; 为什么要引入模板机制?
  6. [POJ]1164 The Castle
  7. linux-ngnix服务(一)
  8. python--内置常用模块
  9. Objective-C 正则表达式使用(1)
  10. cifar-10 图片可视化