P11169 「CMOI R1」Bismuth / Linear Sieve

题目背景

Can you imagine find wakeless,like a satellite,in the black sky?

Somewhere,like a star.

We dream about things way beyond this atmosphere.

At we’re now,on the air.

……

But I eventually evaporates in a blackhole…

Will I just stick up there?……

题目描述

给定以下程序中的 $n$（即输入），求以下伪代码的输出结果。

Input n
For i := 1 to n
	is_not_prime[i] := 0
cntp := 0
counter := 0
For i := 2 to n {
	If is_not_prime[i] = 0 {
		cntp := cntp + 1
		primes[cntp] := i
	}
	For j := 1 to cntp {
		If i * primes[j] > n
			break
		is_not_prime[i * primes[j]] := 1
		If i Mod primes[j] > 0 // should be `If i Mod primes[j] = 0` in Sieve of Euler
			break
		counter := counter + 1
	}
}
Print cntp, counter

请注意此代码不是线性筛，差别在注释过的那一行。

输入格式

一行一个整数，即输入，也就是给定的 $n$。

输出格式

一行两个非负整数，即伪代码输出。

输入输出样例 #1

输入 #1

100

输出 #1

50 30

输入输出样例 #2

输入 #2

9876543

输出 #2

4938272 3092277

输入输出样例 #3

输入 #3

998877665544332211

输出 #3

499438832772166106 312742219398875473

说明/提示

本题采用捆绑测试，并且存在子任务依赖（只有你拿到了一个子任务前一个子任务的分，你才有可能拿到该子任务的分）。

数据范围

$\text{Subtask}$	约束条件	分值
$1$	$n\le 10^7$	$10$
$2$	$n\le 10^9$	$40$
$3$	$n\le 10^{18}$	$50$

对于 $100\%$ 的数据，满足 $1\le n\le 10^{18}$。

C++实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, cnt, ans;
int p[10000005];

signed main()
{
    cin >> n;
    if (n == 1)
        return cout << 0 << ' '<< 0 << '\n', 0;
    cout << (n + 1) / 2 << ' ';
    int now = 2, ans = 0;
    ans = ans + (n / 2 / 2);
    for (int i = 3;; i += 2)
    {
        if ((int)(now / __gcd(now, i) * i > n))
            break;
        now = now / __gcd(now, i) * i;
        ans = ans + (n / i / now);
    }
    cout << ans << '\n';
    return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容