自动搬运

查看原文

来自洛谷，原作者为

	Temp113 You have full control over the entire world.

搬运于2025-08-24 21:18:12，当前版本为作者最后更新于2025-03-25 17:41:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution 1

因为 $1 \le N,M \le 50000$，所以直接枚举 $N \sim N + M$。

对于在此区间的数 $p$，枚举 $2 \sim \sqrt{p}$ 判断，质因子是否大于 $A$。

最后，统计即可。

Code 1

#include<bits/stdc++.h>
using namespace std;
int n, m, a, ans;
bool check(int aa){
	for(int i = 2; i * i <= aa; i++){
		if(!(aa % i) && i > a) return 0;
		while(!(aa % i)) aa /= i;
	}
	if(aa > a) return 0;
	return 1;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie();
	cin >> n >> m >> a;
	for(int i = n; i <= n + m; i++) ans += check(i);
	cout << ans;
	return 0;
}

Solution 2

当然，也可以直接枚举大于 $A$ 的质数（不超过 $N+M$）。

一个数 $p$，若 $q$ 为它的质因子，则一定有：$p=kq$（$k$ 为正整数）。

所以，对于每个大于 $A$ 的质数 $r$，$r$ 的正整数倍中，一定在质因子分解式中，含有 $r$。

最后，统计即可。

Code 2

精控范围：

#include<bits/stdc++.h>
using namespace std;
const int N = 50005;
int n, m, a, ans, tp1, tp2;
bool flg[2 * N];
bool check(int aa){
	for(int i = 2; i * i <= aa; i++) if(!(aa % i)) return 0;
	return 1;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie();
	for(int i = 0; i < 2 * N; i++) flg[i] = 1;
	cin >> n >> m >> a;
	for(int i = a + 1; i <= n + m; i++){
		if(!check(i)) continue;
		tp1 = (n + i - 1) / i;
		tp2 = (n + m) / i;
		for(int j = tp1; j <= tp2; j++) flg[i * j] = 0;
	}
	for(int i = n; i <= n + m; i++) ans += flg[i];
	cout << ans;
	return 0;
}

范围略广：

#include<bits/stdc++.h>
using namespace std;
const int N = 50005;
int n, m, a, ans;
bool flg[2 * N];
bool check(int aa){
	for(int i = 2; i * i <= aa; i++) if(!(aa % i)) return 0;
	return 1;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie();
	for(int i = 0; i < 2 * N; i++) flg[i] = 1;
	cin >> n >> m >> a;
	for(int i = a + 1; i <= n + m; i++){
		if(!check(i)) continue;
		for(int j = 1; j <= (n + m) / i; j++) flg[i * j] = 0;
	}
	for(int i = n; i <= n + m; i++) ans += flg[i];
	cout << ans;
	return 0;
}