记录编号	618447	评测结果	AAAAAAAAAA
题目名称	4467.NOIP-T1-难度	最终得分	100
用户昵称	xuyuqing	是否通过	通过
代码语言	C++	运行时间	1.360 s
提交时间	2026-09-03 19:09:21	内存使用	30.83 MiB

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

const int N = 2114514;

bool isnt_prime[N];
int prime_divide[N];
int prime_divide_size[N];

void init () {
    isnt_prime[1] = true;
    for (int i = 1; i < N; i++) {
        prime_divide[i] = 1;
    }
    for (int i = 2; i < N; i++) {
        if (isnt_prime[i]) {
            continue;
        }
        
        prime_divide[i] = i;
        prime_divide_size[i] = 1;
        
        for (int j = i + i; j < N; j += i) {
            isnt_prime[j] = true;
            prime_divide[j] *= i;
            prime_divide_size[j]++;
        }
    }
}

int t;
int l;
int r;
int res;

bool vis[N];
int set_size[N];

void has_prime_solution () {
    memset (vis, 0, sizeof (vis));
    memset (set_size, 0, sizeof (set_size));
    
    for (int i = l; i <= r; i++) {
        set_size[prime_divide[i]]++;
    }
            
    for (int i = 2; i <= r; i++) {
        if (vis[i] || !set_size[i]) {
            continue;
        }
        
        res += set_size[i] * prime_divide_size[i] + 1;
        vis[i] = true;
        
        for (int j = i + i; j <= r; j += i) {
            if (vis[j] || !set_size[j]) {
                continue;
            }
            
            res += set_size[j] * prime_divide_size[j];
            vis[j] = true;
        }
    }
    
    res -= 2;
}

int dad[N];
int union_size[N];

int find (int id) {
    if (dad[id] == id) {
        return id;
    }
    dad[id] = find (dad[id]);
    return dad[id];
}

void merge (int one, int two) {
    one = find (one);
    two = find (two);
    
    if (one == two) {
        return;
    }
    
    if (union_size[one] > union_size[two]) {
        dad[two] = one;
        union_size[one] += union_size[two];
    }
    else {
        dad[one] = two;
        union_size[two] += union_size[one];
    }
}

bool same (int one, int two) {
    return find (one) == find (two);
}

int gcd (int one, int two) {
    if (two == 0) {
        return one;
    }
    return gcd (two, one % two);
} 

void hasnt_prime_solution () {
    for (int i = l; i <= r; i++) {
        dad[i] = i;
        union_size[i] = 1;
    }
    
    vector<pair<int, pair<int, int> > > graph;
    
    for (int i = l; i <= r; i++) {
        for (int j = i + 1; j <= r; j++) {
            graph.emplace_back(prime_divide_size[i] + prime_divide_size[j] - prime_divide_size[gcd (i, j)], make_pair (i, j));
        }
    }
    
    sort (graph.begin(), graph.end());
    
    for (int i = 0, cc = 0; i < graph.size(); i++) {
        int w = graph[i].first;
        int one = graph[i].second.first;
        int two = graph[i].second.second;
        
        if (same (one, two)) {
            continue;
        }
        
        merge (one, two);
        res += w;
        
        cc++;
        if (cc == (r - l + 1) - 1) {
            break;
        }
    }
}

int main () {
    
    freopen ("noipt.in", "r", stdin);
    freopen ("noipt.out", "w", stdout);
    
    cin >> t;
    init ();
    for (int index = 1; index <= t; index++) {
        cin >> l >> r;
        res = 0;
        
        if (l == 1) {
            for (int i = 2; i <= r; i++) {
                res += prime_divide_size[i];
            }
        }
        else {
            bool has_prime = false;
            for (int i = l; i <= r; i++) {
                if (!isnt_prime[i]) {
                    has_prime = true;
                    break;
                }
            }
                
            if (has_prime) {
                has_prime_solution ();
            }
            else {
                hasnt_prime_solution ();
            }
        }
        
        cout << res << endl;
    }
    
    return 0;
}