E：思维构造

题意  
存在一个 n 点的完全图, 编号 ∈ [1, n]。
对于任意两点 (i,j) 满足 j - i <= k, 那么 (i,j) 之间有一条 边权为 LCM(i,j) 的边
否则 有一条 边权为 GCD(i,j)的边
问 最小生成树

解析
首先看到 n <= 2e5 
不用想,肯定不是图论;
那么从 思维,构造入手
因为是最小生成树 那么 我们肯定要尽可能的取 gcd(i,j) 而不是 lcm(i, j);
从这个点出发，我们可以想到，1 与 所有数的 gcd 都是 1
那么 我们尽可能的让 1 与 所有的 能连 gcd 的边连上边权为 1 (因为 j - i > k 其中 i 取 1 的时候能够尽可能的让 j 更小)
此时 1 周围的边只能填 lcm ？ 
不是，选择最大的在 n 的范围内的质数 (同理 因为已经让 1 跟大的数进行连 1 边, 那么靠近 1 的边 只能由 mx 来更新,所以让 j 尽可能大)
如此一来 尽可能的选择多的点与 mx 这个最大的质数相连
有些点不满足 与 mx - i > k 那么只需要暴力遍历 [k + i + 1, n] 这个区间 取一个这些点与 i gcd 的 min 作为答案即可
因为 质数之间的距离 增长不大于sqrt(p)log p;
所以可以暴力遍历 因为 遍历的数不会很多 大约为 100;
最后所有没有连上边的点 再与 1 连 lcm 即可 

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define x first
#define y second
using namespace std;
const int maxN = 2e5 + 10;
const int maxM = 2e5 + 10;
const int INF = 1e18;
const int mod = 998244353;
inline int read()
{
    int ans=0,f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return f?-ans:ans;
}
int n,k;
int cnt;
bool st[maxN];
int prime[maxN];
void get_primes(int n)
{
    st[1] = true;
    for(int i = 2 ; i <= n ; i++)
    {
        if(!st[i]) prime[++cnt] = i;
        for(int j=1 ; prime[j] <= n / i ; j++)
        {
            st[prime[j]*i] = true;
            if(i % prime[j] == 0) break;
        }
    }
}
int vis[maxN];
signed main()
{
    get_primes(2e5 + 5);
    n = read(), k = read();
    int ans = 0;
    int mx = 0;
    for(int i = 1 ; i <= n ; i++) 
        if(prime[i] > n)
        { 
            mx = prime[i - 1];
            break;
        }
    if(mx - 1 > k) ans += 1, vis[mx] = 1;
    for(int i = 2 ; i <= n ; i++)
        if(i - 1 > k && vis[i] == 0) ans += 1, vis[i] = 1;
    for(int i = 2 ; i <= n ; i++)
    {    
        if(mx - i > k && vis[i] == 0)
        {
            ans += 1;
            vis[i] = 1;
        }
        else if(mx - i <= k && vis[i] == 0)
        {
            int res = INF;
            for(int j = k + i + 1 ; j <= n ; j++)
                res = min(gcd(j,i), res);
            if(res != INF)
            {
                ans += res;
                vis[i] = 1;
            }
        }
    }
    for(int i = 2 ; i <= n ; i++)
        if(vis[i] == 0) ans += i;
    printf("%lld\n",ans);
    system("pause");
    return 0;
}