题解 | A - GCD

考虑数的唯一分解

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1e7 + 10, M = 2e6 + 10, inf = 0x3f3f3f3f;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res &lt;&lt; 3) + (res &lt;&lt; 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

bool flag[N];

int n, m, cnt, prime[N];

long long res[N], ans;

void init(int N) {
    for (int i = 2; i &lt;= N; i++) {
        if (!flag[i]) {
            prime[++cnt] = i; res[i] = i; long long t = i;
            while (t &lt;= 10000000ll) res[t] = i, t *= i;
        }
        for (int j = 1; j &lt;= cnt &amp;&amp; 1ll * i * prime[j] &lt;= 1ll * N; j++) {
            flag[i * prime[j]] = 1; if (i % prime[j] == 0) break;
        }
    }
}

int main() {
    int l = read(), r = read();
    for (int i = l; i &lt;= r; i++) res[i] = 1;
    init(10000000);
    for (int i = l; i &lt;= r; i++) ans += res[i];
    printf("%lld", ans);
    return 0;
}
```</queue></algorithm></cstring></cmath></cstdio></iostream>