TJ-CF1423K

CF1423K

首先，我们假设 \(a>b\) ，设 \(\gcd(a,b)=c,a=k_1\times c,b=k_2\times c\)
则 \(c\le b<a\)

则是 \(c,k_1,k_2\) 构成一个三角形，且 \(k_1>k_2(k_1>1)\)

分类讨论：

1. \(c\) 为最大值

   \(c<k_1+k_2,c>k_1>k_2\)

   由于 \(c,k_1,k_2\) 都为正整数，也就是说只要 \(c>2\) 就有可能的一组 \(k_1,k_2\)

2. \(k_1\) 为最大值

   \(k_1>c,k_1<c+k_2\)

   若 \(k_2=k_1-1\) ，则只要 \(c>1\) 即可，也就是说要 \(a,b\) 不互质。

3. \(c=k_1(k_1>1)\)

   \(k_1+k_2>c\) ，则 \(k_2>0\) ，只要 \(a,b\) 不互质即可。

那么，当 \(a\) 取什么值的时候，对于任意一个 \(1\le b<a\) ， \(\gcd(a,b)\) 都为1呢？

显然是质数时，也就是说，合数一定不会是孤独数字

接下来单独考虑质数的情况，设 \(a\) 为质数， \(b=k\times a\)

则 \(\gcd(a,b)=a\) ，三角形三边为 \(a,k,1(a\ge 2)\)

1. \(a\) 为最大值

   则 \(a<k+1\) ， \(a>k\) ，矛盾。

2. \(k\) 为最大值

   则 \(k<a+1\) ， \(k>a\) ，矛盾。

3. \(a=k\)

   显然满足 \(k<a+1~(k=a)\) 。此时 \(b=a^2=k^2\) ，只有在 \(a\le \sqrt{n}\) 时成立。

设 \(f[i]\) 表示 \([1,i]\) 中的质数的数量，则最后答案为 \(f[n]-f[\sqrt{n}]\)

代码：

#include<bits/stdc++.h> 
#define ll long long 
using namespace std;
const int N=1e6+6;
bool vis[N];
int prime[N],cnt;
int sum[N];
inline void work(){
	for(int i=2;i<N;i++){
		if(!vis[i]){
			prime[++cnt]=i;
			sum[i]=1;
		}
		for(int j=1;j<=cnt&&prime[j]*i<N;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}
	for(int i=1;i<N;i++) sum[i]+=sum[i-1];
}

int main(){	
	work();
	int T,n;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		printf("%d\n",sum[n]-sum[(int)sqrt(n)]+1);
	}
	return 0;
}