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

· · 题解

题目简述

给定 N,M,A，求 [N,N+M] 中所有质因数都小于等于 A 的数的个数。

主要思路

可以直接按题意模拟，求 n 的所有质因数，就可以遍历 i \in [2,n]，重复直到 n \bmod i \neq 0，n \gets \frac{n}{i}。这样 n 除以的所有数都一定是质数，因为合数也由若干个质因数相乘组成，而这些质因数都小于这个合数。等遍历到合数时，n 与这个合数原先的公质因数早就在之前被除完了，公因数同理，这个合数也一定不是 n 的因数。

为了优化代码，i 只需在 [2,A] 这个区间即可，并且只能在这个区间，否则会 TLE。最后判断如果 n=1，就使答案加 1。

AC Code

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
typedef long double db;
const int INT_INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
// ----------------------------

// ----------------------------

// ----------------------------

int main() {
    int n, m, a; scanf("%d %d %d", &n, &m, &a);
    // ----------------------------
    int j, k, ans = 0;
    for (int i = n; i <= n + m; i++) {
        k = i;
        for (j = 2; j <= a && k > 1; j++) {  // 当 k 的所有质因数都被除完时，可以直接结束循环，进一步优化代码
            while (k % j == 0) k /= j;
        }
        ans += (k == 1);
    }
    // ----------------------------
    printf("%d", ans);
    return 0;
}