LibreOJ #6165. 一道水题
2024-08-27 06:26:38
二次联通门 : LibreOJ #6165. 一道水题
/*
LibreOJ #6165. 一道水题 欧拉线性筛
其实题意就是求区间[1, n]所有数的最小公倍数 那么答案就是所有质因子最大幂次的乘积 水题开心。。
*/
#include <cstdio>
#include <iostream> #define Max 100000290 int prime[Max], Count;
bool is_prime[Max]; long long Euler_Line_Sieve (const int &N)
{
#define Mod 100000007
register int i, j; is_prime[] = true;
long long res, Answer = ;
for (i = ; i <= N; ++ i)
{
if (is_prime[i] == false)
{
prime[++ Count] = i;
for (res = i; res * (long long) i <= N; res *= i);
Answer = (Answer * res) % Mod;
}
for (j = ; j <= Count && i * prime[j] <= N; ++ j)
{
is_prime[i * prime[j]] = true;
if (i % prime[j] == )
break;
}
}
#undef Mod
return Answer;
}
int Main ()
{
int N;
scanf ("%d", &N);
long long Answer = Euler_Line_Sieve (N); printf ("%lld", Answer);
return ;
} int ZlycerQan = Main ();
int main (int argc, char *argv[]) {;}
最新文章
- win7 下安装RVCT
- CSS 的定位方式和含义
- mysql-linux命令登录,退出
- Ubuntu下root密码认证错误
- Maven管理
- Uva10635 LCS
- BZOJ4605 : 崂山白花蛇草水
- backbonejs中的模型篇(二)
- 如何查看IIS并发连接数
- ASP.NET缓存 Cache之数据缓存
- Android利用setLayoutParams在代码中调整布局(Margin和居中)
- 再谈php乱码问题
- Web前端优质学习网站
- Chapter 1 First Sight——25
- shell编程值之正则表达式与字符截取(6)
- Dev、GridControl的模糊查询
- 时间序列数据库调研之InfluxDB
- jmeter解决request response中文乱码问题
- ES系列六、ES字段类型及ES内置analyzer分析
- 20155238 《JAVA程序设计》实验三(敏捷开发与XP实践)实验报告