傳送門
思路：根據三角形性質，我們容易得到：
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 - p < p^2 < a + b,得到非質數的奇數一定成立
所以答案就是p[n] - p[sqrt(n)]（p[N]表示數字N之前有幾個質數，包括N）
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cstring> 5 #include <vector> 6 #include <set> 7 8 using namespace std; 9 10 #define ll long long 11 #define pb push_back 12 #define fi first 13 #define se second 14 #define lson(rt) (rt << 1) 15 #define rson(rt) (rt << 1 | 1) 16 17 const int N = 1e6 + 10; 18 int vis[N], is_p[N]; 19 20 void fun() 21 { 22 vis[1] = 1; 23 for(int i = 2; i < N; ++i) { 24 if(vis[i]) continue; 25 vis[i] = 1; 26 is_p[i] = 1; 27 for(int j = i + i; j < N; j += i) vis[j] = 1; 28 } 29 30 for(int i = 1; i < N; ++i) is_p[i] += is_p[i - 1]; 31 } 32 33 void solve() 34 { 35 fun(); 36 int T; 37 scanf("%d", &T); 38 while(T--) { 39 int n; 40 scanf("%d", &n); 41 42 printf("%d\n", is_p[n] - is_p[(int)sqrt(double(n))] + 1); 43 } 44 } 45 46 47 int main(){ 48 49 solve(); 50 51 return 0; 52 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/181272.html
標籤：其他
下一篇：可靠資料傳輸基本原理（1）