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

小码匠

发布于 2022-08-08 13:14:37

4160

发布于 2022-08-08 13:14:37

文章被收录于专栏：小码匠和老码农

对话

老码农：今天做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:

输出

Print the answer as an integer.

输入示例 1

输出示例 1

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

输出示例 2

输入示例 3

123456789012345

输出示例3

题解

小码匠题解

#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;
}

参考题解

#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大神）

#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大神）

#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("%lld\n", ans);
}

参考题解（drken大神）

drken大神的题解非常棒，是我的最爱；
第29行是个没有用处的语句。

#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;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-06-25，如有侵权请联系 cloudcommunity@tencent.com 删除

format

input

integer

本文分享自小码匠和老码农微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

format

input

integer

登录后参与评论

0 条评论

热度