文章目录
  1. 1. LOJ6165
    1. 1.1. 题目描述
    2. 1.2. 分析
    3. 1.3. 代码

引言:线性筛的一道题。传送门:LOJ6165


LOJ6165

题目描述

一天,szb 在上学的路上遇到了灰太狼。

灰太狼:帮我们做出这道题就放了你。
szb:什么题?
灰太狼:求一个能被[1,n]内所有数整除的最小数字,并对1e8+7取模。
szb:这题太水了,就让我小弟来做好了。

然后你就光荣的接受了这个任务。

分析

显然,本题是求1~n的最小公倍数。

无脑想法是求1~n的gcd,然后:

lcm=x=1nxgcd\small{\text{lcm}}=\prod_{x=1}^n \frac {x}{\small{\text{gcd}}}

但它成立吗?我们知道两个数的情况下,下式成立:

lcm(a,b)=abgcd(a,b)lcm(a,b)=\frac {ab}{gcd(a,b)}

但实际上不能推广到多个数,因此上述无脑想法是不成立的。

算术基本定理:任何大于1的自然数,都可以表示成有限个素数(可以重复)的乘积,并且如果不计次序的话,表法是唯一的。

根据算数基本定理,我们可以将任意的数拆成小于它的素数的乘积,记pip_i为素数。

a=p1a1p2a2...pkaka=p_1^{a_1}*p_2^{a_2}*...*p_k^{a_k}

b=p1b1p2b2...pkbkb=p_1^{b_1}*p_2^{b_2}*...*p_k^{b_k}

其中aia_ibib_i可以为0。

易得的,我们可以如下表示lcm:

lcm(a,b)=p1max(a1,b1)p2max(a2,b2)...pkmax(ak,bk)lcm(a,b)=p_1^{\max(a_1,b_1)}*p_2^{\max(a_2,b_2)}*...*p_k^{\max(a_k,b_k)}

因此我们考虑对所有的小于n的素数pip_i,求不超过n的picip_i^{c_i},然后再求积即可,cic_i可以不断迭代获得。

一定要用线性筛,埃氏筛会炸的。传送门:素数筛

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n;
const ll mod = 100000007;
#define maxn 100000010
bool vis[maxn];
int prime[6000010];

int main(){
scanf("%lld",&n);
int i=0;
ll ans=1;
int cnt=0;
for(int i=2;i<=n;i++){
if(!vis[i]){
prime[cnt++]=i;
ll j;//一定要ll
for(j=i;j*i<=n;j=j*i%mod);//有模操作时,一定不要简写成j*=i%mod。
ans=ans*j%mod;
}
for(int j=0;j<cnt;j++){
int k=i*prime[j];
if(k>n)break;
vis[k]=1;
if(i%prime[j]==0)break;
}
}
printf("%lld\n",ans%mod);
return 0;
}
文章目录
  1. 1. LOJ6165
    1. 1.1. 题目描述
    2. 1.2. 分析
    3. 1.3. 代码