题目描述
blablabla
样例
//https://www.luogu.com.cn/record/150167786
//////埃氏筛法 + 并查集
#include <bits/stdc++.h>
using namespace std;
//拥有大于等于p的公共质因数,,筛质数,,埃氏筛法,,找因数
const int N = 1E5 +11;
int f[N], a, b, p;
bool st[N];
int find(int x){
return f[x] = (f[x] == x ? x : find(f[x]));
}
int main(){
//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 取消同步留会快很多,10000个输入
cin >> a >> b >> p;
for(int i = a; i <= b; ++ i) f[i] = i;
int ans = b - a + 1;// 初始最多集合数,,各自一个
for(int i = 2; i <= b; ++ i){ ////埃氏筛法,从2开始筛
if(!st[i]){//埃氏筛先判断有没有被筛掉过--是质数的话
if(i >= p){//质数大于等于p
for(int j = 2 * i; j <= b; j += i){
st[j] = true;
if(j - i >= a && find(j) != find(j - i)){
f[find(j)] = find(j - i);
ans --; //合并一个少一个
}
}
}
else {
for(int j = 2 * i; j <= b; j += i) st[j] = true;
}///筛掉不合法且非质数的数
}
}
cout << ans << '\n';
system("pause");
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla