题解：B4266 [朝阳区小学组 2019] factorization

Temp113 · 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;
}