线性筛+数学规律
前两天刚学了线性筛,拿这题练练手
开始的思路是:
- 先求出1-n所有的素数,
- 然后用再遍历一遍去掉所有素数的幂次方,剩下的数就是没有被吃掉的
- 再求出所有没有被吃掉数的最小公倍数;
显然TLE了,数据量是1.6e8,太大了,数稍微大点,两步都求不完就卡死了;但是做的过程中发现了求n个数最小公倍数的算法,也算学到了点东西(这个题不必先求n个没被吃掉的数,再求这n个数的最小公倍数,后面讲)
介绍一个初中的定理(我竟然没印象):
对于两个整数(a, b),它们的最小公倍数是(LCM),最大公约数是(GCD),那么有如下定理:(a*b = LCM*GCD)
比如对两个数(24=2*2*2*3, 18=2*3*3),最大公约数为(2*3=6),最小公倍数为(2^3 * 3^2 = 72),有(24*18 = 6*72)
求两个整数的最大公约数可以用辗转相除法,所以求两个数的最小公倍数就可以使用(LCM = a*b/GCD),对于(n)个数,则依次计算即可。
放一下TLE的代码:
// 这个代码tle了,思路就是先求出所有素数,然后再求出所有剩余数
// 再计算所有剩余数的最小公倍数
#include<bits/stdc++.h>
#define ll long long
//#define mod 1e9+7
const ll mod = 1e9+7;
#define N 160000010
using namespace std;
int n;
//int prime[N];
//int left[N];
int visited[N];
vector<int> prime;
vector<ll> rest;
// 辗转相除法求最大公约数
int gcd(int a, int b)
{
return 0;
}
// 计算1-n所有素数存到prime中
void calPrime(int n)
{
for(int i=2; i<=n; ++i){
if(!visited[i]){
prime.push_back(i);
}
for(int j=0; j<prime.size() && 1ll*i*prime[j]<=n; ++j){
visited[i*prime[j]] = 1;
if(i%prime[j]==0) break;
}
}
}
// 计算所有剩下的数
void calLeft(int n)
{
for(int i=2; i<=n; ++i){
if(visited[i]==0){ // 这个数是质数
for(int j=i; j<=n; j*=i){
visited[j] = 2; // 青蛙跳过的都标记成2
}
}
else if(visited[i]==1){ //
rest.push_back(i);
}
}
//
for(int i=0; i<rest.size(); ++i) {
printf("%d ", rest[i]);
}
}
int main()
{
scanf("%d", &n);
calPrime(n);
// cout << "calPrime finished
";
calLeft(n);
ll ans;
if(rest.size() == 0) printf("empty");
else {
ans = rest[0];
for(int i=1; i<rest.size(); ++i){
ans = (ans / __gcd(ans, rest[i])) *rest[i] % mod;
}
printf("%d", ans);
}
return 0;
}
正确做法:
这其实就是线性筛+数学规律题
首先观察一下1-n之内被吃掉的数的特点:
-
1被吃掉了
-
所有的素数被吃掉了
-
所有素数的幂次方被吃掉了
那么剩下的数有什么特点呢?
答案就是:剩下的数都是因子中含有两个或者两个以上不同因子的数(如6=3*3, 12=2*2*3)
我们要对1-n中所有这样的数(含有两个或者两个以上不同因子的数)求最小公倍数。这该怎么求呢?
simple1:
对于两个剩下的数:(2^3 * 3^2, 2*3^3),其最小公倍数一定是每个质数因子取最大幂然后相乘 ,例子中的最小公倍数为(2^3*3^3)
则对于任意一个小于n的剩下的数,其一定可以用(1-dfrac{n}{2})中多个质数相乘表示。
那我们想求出所有剩下数的最小公倍数,只需要求出 (1-dfrac{n}{2})中每个质数的最大幂,然后将它们相乘即可。而一个质数想要取最大幂,有以下两种情况:
- 这个质数是2:那可以有({2*3, 2^2*3, 2^3*3, ...,2^k*3} le n);对于2,其最大幂就是:(2^{k_2} le n)
- 这个质数是(x(x ot=2)): 可以有({x*2, x^2*2, x^3*2, ...,x^k*2} le n);其最大幂就是:(x^{k_x} le n)
假设我们求得(1-dfrac{n}{2})所有质数为(p[1..m]),那我们所求的结果就是:(prod_{i=1}^m p[i]^{k_{p[i]}})
ac代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
const int N=8e7+7; // 最大素数是 n/2
int prime[N];
int visited[N];
int cnt = 0;
ll ans = 1;
int n;
// 只需要求n/2以内的素数就行,因为这个题目特殊,需要两个不同的质数相乘
void table(int n)
{
for(int i=2; i<=n/2; ++i){
if(!visited[i]) prime[cnt++]=i;
for(int j=0; j<cnt && 1ll*i*prime[j]<=n/2; ++j) {
visited[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
int main()
{
scanf("%d", &n);
table(n); // 求出n/2以内的所有质数,放到prime[]中
ll t;
//
t=2;
while(t*3<=n) t*=2;
ans = (ans*(t/2))%mod;
//
for(int i=1; i<cnt; ++i){
t=prime[i];
while(t*2<=n) t*=prime[i];
ans = (ans*(t/prime[i]))%mod;
}
if(ans<6) printf("empty
");
else printf("%lld
", ans);
return 0;
}