【小码匠自习室】重做ABC250-D, 我无力反抗

2022-08-08 13:14:37 浏览数 (1)

对话

老码农：今天做ABC250-D那道题吧，如何？

小码匠：那道题我们刚做完吗？我也优化了，也AC了。

还有那个破题目，也不知道出题人咋想的，250，谁喜欢这个数字啊。

老码农：对，是AC了，执行时间对比，40倍的耗时差距。

代码编写者

执行耗时

小码匠

778ms

heno239大神

25ms

yokozuna57大神

18ms

小码匠：呵呵哒（老码农是个数据控...）。

老码农：你，你怎么不明白我的良苦用心呢？

  • 一：你要成为码匠，必须要有精益求精的精神，不能局限于把题做出来了，要不断拓展思路，提升自己的技术能力；
  • 二：再做一遍，也是结合你最近学的算法，再精进一把。

小码匠：唐·老爸·僧，说不过你，我去码代码。

老码农：把那个“唐”字去掉，又想说我“唐僧”，胆肥了你...

碎碎念

  • 动用了我小码匠的洪荒之力，优化到了30ms，需要闭关静心思考...

标签

  • 质数、累计和、二分查找

题目地址

  • D - 250-like Number
    • https://atcoder.jp/contests/abc250/tasks/abc250_d

题目描述

Let us regard an integer k as "similar to 250" if the following condition is satisfied:

  • k is represented as k=p with primes p<q.

How many integers less than or equal to N are "similar to 250"?

约束条件

  • N 是1到10(inclusive)整数

输入

Input is given from Standard Input in the following format:

代码语言：javascript复制
N

输出

Print the answer as an integer.

输入示例 1

代码语言：javascript复制
250

输出示例 1

代码语言：javascript复制
2
  • 54 = 2 is "similar to 250".
  • 250 = 2 times 5^3 is "similar to 250".

The two integers above are all the integers "similar to 250".

输入示例 2

代码语言：javascript复制
1

输出示例 2

代码语言：javascript复制
0

输入示例 3

代码语言：javascript复制
123456789012345

输出示例3

代码语言：javascript复制
226863

题解

小码匠题解

代码语言：javascript复制
#include <bits/stdc  .h>

using namespace std;
#define endl 'n';

void coder_solution();

void best_solution();

int main() {
    // 小码匠
    coder_solution();

    // 最优解
    //best_solution();
    return 0;
}

void coder_solution() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 输入
    long long n;
    cin >> n;
    vector<long long> vi;
    int loop_count = cbrt(n);
    vector<bool> tf(1000001, true);
    tf[0] = false;
    tf[1] = false;
    vi.push_back(2);

    for (int i = 3; i <= loop_count; i  = 2) {
        if (tf[i]) {
            for (int j = 3; j * i <= loop_count; j  = 2) {
                tf[j * i] = false;
            }
            vi.push_back(i);
        }
    }
    int len = vi.size();
    int ans = 0;
    for (int i = 0; i < len - 1;   i) {
        for (int j = i   1; vi[j] * vi[j] * vi[j] <= n / vi[i] && j < len;   j) {
            ans  ;
        }
    }
    cout << ans;
}

参考题解

代码语言：javascript复制
#include <bits/stdc  .h>
#define pb push_back
#define int long long
using namespace std;
const int maxn = 1e6   9;
bitset<maxn> pri;
int nums[maxn], k = 0;
 
void getprimes(int n)
{
	pri[0] = pri[1] = 1;
	for(int i = 2;i <= n / i;    i)
		if(!pri[i])for(int j = i * i;j <= n; j  = i)pri[j] = 1;
	for(int i = 1;i <= n;    i)if(!pri[i])nums[   k] = i;
}
 
 
signed main()
{
	int N;cin >> N;
	int top = pow(N, 0.33);
	getprimes(top);
	int ans = 0;
	for(int i = 1;i <= k;    i)
	{
		int q_3 = nums[i] * nums[i] * nums[i];
		int pos = upper_bound(nums   1,nums   i, N * 1.0 / q_3) - 1 - nums;
		ans  = pos;
	}
	cout << ans << 'n';
	return 0;
}

参考题解（SSRS大神）

代码语言：javascript复制
#include <bits/stdc  .h>

using namespace std;

int main() {
    long long N;
    cin >> N;
    vector<long long> prime;
    int x = 2;
    while (true) {
        if (x > 1000000) {
            break;
        }
        bool ok = true;
        for (int i = 2; i * i <= x; i  ) {
            if (x % i == 0) {
                ok = false;
                break;
            }
        }
        if (ok) {
            prime.push_back(x);
        }
        x  ;
    }
    int cnt = prime.size();
    long long ans = 0;
    for (int i = 0; i < cnt; i  ) {
        long long X = N / prime[i] / prime[i] / prime[i];
        ans  = upper_bound(prime.begin(), prime.begin()   i, X) - prime.begin();
    }
    cout << ans << endl;
}

参考题解（apiad大神）

代码语言：javascript复制
#include <bits/stdc  .h>

using namespace std;
#define rep(i, a, n) for (int i=a;i<n;i  )
#define per(i, a, n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int, int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod = 1000000007;

int rnd(int x) { return mrand() % x; }

ll powmod(ll a, ll b) {
    ll res = 1;
    a %= mod;
    assert(b >= 0);
    for (; b; b >>= 1) {
        if (b & 1)res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
// head

const int N = 1010000;
int M = 1000000;
ll n, ans;
int isp[N], s[N];

int main() {
    scanf("%lld", &n);
    rep(i, 2, M   1) isp[i] = 1;
    for (int i = 2; i <= M; i  )
        if (isp[i]) {
            for (int j = 2 * i; j <= M; j  = i) isp[j] = 0;
        }
    rep(i, 2, M   1) s[i] = s[i - 1]   isp[i];
    rep(q, 2, M   1) if (isp[q]) {
            ans  = s[min((ll) q - 1, n / q / q / q)];
        }
    printf("%lldn", ans);
}

参考题解（drken大神）

  • drken大神的题解非常棒，是我的最爱；
  • 第29行是个没有用处的语句。
代码语言：javascript复制
#include <bits/stdc  .h>
using namespace std;

vector<int> Era(int n) {
    vector<int> res;
    vector<bool> isprime(n, true);  // ふるい
    isprime[0] = false; isprime[1] = false;
    for (int i = 2; i < n;   i) isprime[i] = true;
    for (int i = 2; i < n;   i) {
        if (isprime[i]) {
            res.push_back(i);
            for (int j = i*2; j < n; j  = i) {
                isprime[j] = false;
            }
        }
    }
    return res;
}

int main() {
    long long N;
    cin >> N;

    // エラトステネスのふるい
    vector<int> prs = Era(1000000);

    long long res = 0;
    for (long long q : prs) {
        if (q * q * q > N) break;

        long long pmax = min(q - 1, N / q / q / q);

        // pmax 以下の素数の個数を二分探索で求める
        long long low = -1, high = prs.size();
        while (high - low > 1) {
            long long x = (low   high) / 2;
            if (prs[x] > pmax) high = x;
            else low = x;
        }
        res  = high;
    }
    cout << res << endl;
}
format input integer

0 人点赞