题目大意:给定一个有理数$A$,定于$S$为小于等于$N$的质数个数,$T$为小于等于$N$的回文数的个数。求一个最大的正整数$N$使得$Sle AT$。
题解
由质数定理,$Sapprox frac{N}{ln N}$,且容易看出$Tapprox sqrt N$(前一半等于后一半,一半的长度相当于开方)。可以推测$N$足够大时,$S>T$。
所以可以在一个范围内枚举。因为$Ale 42$,所以可以根据这个极端情况调整最大枚举的$N$的大小。大概是2e6以内。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
|
#define INF 2000000000 using namespace std; typedef long long ll; int (){ int f = 1, x = 0; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); } while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar(); return f * x; } int p, q; int prime[1000005], tot = 0, ans = 1; bool vis[2000005] = {0}; void init(){ p = read(), q = read(); } bool ispali(int x){ if(x < 10) return true; int t = 10; while(x >= 10 * t) t *= 10; while(t >= 10){ if(x % 10 != x / t) return false; x %= t, x /= 10, t /= 100; } return true; } void solve(){ for(int i = 2; i <= 2000000; ++i){ if(!vis[i]) prime[++tot] = i; for(int j = 1; j <= tot; ++j){ if(1ll * prime[j] * i > 2000000ll) break; vis[i * prime[j]] = true; if(i % prime[j] == 0) break; } } int cur = 1, sum1 = 1, sum2 = 0; for(int i = 2; i <= 2000000; ++i){ if(ispali(i)) sum1++; if(cur <= tot && prime[cur] == i) sum2++, cur++; if(1ll * q * sum2 <= 1ll * p * sum1) ans = max(ans, i); } printf("%dn", ans); } int main(){ init(); solve(); return 0; }
|
近期评论