CF 1423 K. Lonely Numbers（数学 + 思维）

传送门

 

思路：根据三角形性质，我们容易得到：

a + gcd(a, b)^2 > b

a + b > gcd(a, b)^2

b + gcd(a, b)^2 > a

推出： a - b < gcd(a, b)^2 < a + b ①

假设a为偶数，可以得到 a + 2或者a - 2与a配对一定满足 2 < 4 < x(>= 6),得到偶数一定成立

假设a为奇数：

如果a为质数p，若需要满足①，则必须 p^2 - p < p^2 < p^ + p，得到(p，p^2)为一对

如果a不为质数，则a可以表示为若干个素数相乘（唯一分解定理），我们选择最小的质数，则 a = p * Y,则a + p 或者 a - p可以与a配对，

即 a + p - a < p^2 < a + b,得到非质数的奇数一定成立

所以答案就是p[n] - p[sqrt(n)]（p[N]表示数字N之前有几个质数，包括N）

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lson(rt) (rt << 1)
#define rson(rt) (rt << 1 | 1)

const int N = 1e6 + 10;
int vis[N], is_p[N];

void fun()
{
    vis[1] = 1;
    for(int i = 2; i < N; ++i) {
        if(vis[i]) continue;
        vis[i] = 1;
        is_p[i] = 1;
        for(int j = i + i; j < N; j += i) vis[j] = 1;
    }

    for(int i = 1; i < N; ++i) is_p[i] += is_p[i - 1];
}

void solve()
{
    fun();
    int T;
    scanf("%d", &T);
    while(T--) {
        int n;
        scanf("%d", &n);
        
        printf("%d
", is_p[n] - is_p[(int)sqrt(double(n))] + 1);
    }
}

 
int main(){

    solve();
    
    return 0;
}