当前位置：首页 > news >正文

【数论】P11169 「CMOI R1」Bismuth / Linear Sieve|普及+

news 2025/6/29 12:32:19

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 nis_not_prime[i] := 0
cntp := 0
counter := 0
For i := 2 to n {If is_not_prime[i] = 0 {cntp := cntp + 1primes[cntp] := i}For j := 1 to cntp {If i * primes[j] > nbreakis_not_prime[i * primes[j]] := 1If i Mod primes[j] > 0 // should be `If i Mod primes[j] = 0` in Sieve of Eulerbreakcounter := counter + 1}
}
Print cntp, counter

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

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

输出 #1

50 30

输入输出样例 #2

输入 #2

输出 #2

4938272 3092277

输入输出样例 #3

输入 #3

998877665544332211

输出 #3

499438832772166106 312742219398875473

说明/提示

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

数据范围

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

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

数论

$n == 1 是特殊处理$ ，返回{0,0}。
性质一：prime数组包括2，不包括1。包括所有大于2的奇数，不包括所有大于2的偶数。

 伪代码
is_not_prime[i * primes[j]] := 1

如果i是偶数，则i * primes[j]是偶数。
如果i是奇数，则只执行一次,j为1，而primes[1]是2，故其乘积也是偶数。
任意偶数 $n$ ，则 $i == n /2$ 时，设置为非质数。
故第一问的答案： $(n + 1) /2$
那些i,counter 增加0次？
答：不是2的倍数，即i是奇数。
那些i,counter增加1次？
答：是2的倍数，不是3倍数。
性质二：counter 增加k次。
是prime[0…k-1]的倍数，不是prime[k]的倍数。
令x = lcm(prime[0…k-1]),y=lcm(prime[0…k])
某i是x的倍数不是y的倍数。
则：它是prime[0]的倍数，prime[1]的倍数,是prime[2]的倍数 $\cdots$ ,各+1，共加k次。
如果x > n，则无需枚举。
最小的70个质因数的最小公倍数一定大于m。故prime的长度不会超过1000个，具体跑一下程序是发现长度是23。
第二问的结果是： $\sum(\frac n {prime[i] \times 对应的x})$ 23个数的调和奇数 < 8，故long long不会溢出。
求a和b的最小公倍数，可能溢出。g = gcd(a,b) 如果n / a < b/g 则会溢出。

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>
#include<array>#include <bitset>
#include <chrono>
using namespace std::chrono;
using namespace std;template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;
}template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t);return in;
}template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;
}template<class T1, class T2, class T3, class T4, class T5, class T6, class T7 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4, T5, T6, T7>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >> get<5>(t) >> get<6>(t);return in;
}template<class T = int>
vector<T> Read() {int n;cin >> n;vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}
template<class T = int>
vector<T> ReadNotNum() {vector<T> ret;T tmp;while (cin >> tmp) {ret.emplace_back(tmp);if ('\n' == cin.get()) { break; }}return ret;
}template<class T = int>
vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}template<int N = 1'000'000>
class COutBuff
{
public:COutBuff() {m_p = puffer;}template<class T>void write(T x) {int num[28], sp = 0;if (x < 0)*m_p++ = '-', x = -x;if (!x)*m_p++ = 48;while (x)num[++sp] = x % 10, x /= 10;while (sp)*m_p++ = num[sp--] + 48;AuotToFile();}void writestr(const char* sz) {strcpy(m_p, sz);m_p += strlen(sz);AuotToFile();}inline void write(char ch){*m_p++ = ch;AuotToFile();}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);m_p = puffer;}~COutBuff() {ToFile();}
private:inline void AuotToFile() {if (m_p - puffer > N - 100) {ToFile();}}char  puffer[N], * m_p;
};template<int N = 1'000'000>
class CInBuff
{
public:inline CInBuff() {}inline CInBuff<N>& operator>>(char& ch) {FileToBuf();while (('\r' == *S) || ('\n' == *S) || (' ' == *S)) { S++; }//忽略空格和回车ch = *S++;return *this;}inline CInBuff<N>& operator>>(int& val) {FileToBuf();int x(0), f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行		return *this;}inline CInBuff& operator>>(long long& val) {FileToBuf();long long x(0); int f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行return *this;}template<class T1, class T2>inline CInBuff& operator>>(pair<T1, T2>& val) {*this >> val.first >> val.second;return *this;}template<class T1, class T2, class T3>inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val);return *this;}template<class T1, class T2, class T3, class T4>inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);return *this;}template<class T = int>inline CInBuff& operator>>(vector<T>& val) {int n;*this >> n;val.resize(n);for (int i = 0; i < n; i++) {*this >> val[i];}return *this;}template<class T = int>vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {*this >> ret[i];}return ret;}template<class T = int>vector<T> Read() {vector<T> ret;*this >> ret;return ret;}
private:inline void FileToBuf() {const int canRead = m_iWritePos - (S - buffer);if (canRead >= 100) { return; }if (m_bFinish) { return; }for (int i = 0; i < canRead; i++){buffer[i] = S[i];//memcpy出错			}m_iWritePos = canRead;buffer[m_iWritePos] = 0;S = buffer;int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);if (readCnt <= 0) { m_bFinish = true; return; }m_iWritePos += readCnt;buffer[m_iWritePos] = 0;S = buffer;}int m_iWritePos = 0; bool m_bFinish = false;char buffer[N + 10], * S = buffer;
};class Solution {
public:long long Ans(long long n) {long long x = 2;vector<long long> prime = { 2 };vector<long long> xs = { 2 };for (long long i = 3; ; i += 2) {const auto g = gcd(x, i);if (n / x < i / g) { break; }x = x * (i / g);prime.emplace_back(i);xs.emplace_back(x);}long long ans = 0;for (int i = 0; i < xs.size(); i++) {ans += n / prime[i] / xs[i];}return ans;}
};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG	ios::sync_with_stdio(0); cin.tie(nullptr);//CInBuff<> in; COutBuff<10'000'000> ob;long long N;cin >>N  ;if (1 == N) { cout << "0 0"; return 0; }
#ifdef _DEBUG	//printf("M=%d", M);//Out(as, ",as=");//Out(ps, ",ps=");//Out(ss, ",ss=");//Out(ope, ",ope=");
#endif // DEBUG		auto res = Solution().Ans(N);cout << (N+1)/2 << " "<<res << "\n";return 0;
}

单元测试

TEST_METHOD(TestMethod1){	auto res = Solution().Ans(1e18);AssertEx(313093615151009041LL, res);}TEST_METHOD(TestMethod2){auto res = Solution().Ans(100);AssertEx(30LL, res);}TEST_METHOD(TestMethod3){auto res = Solution().Ans(9876543LL);AssertEx(3092277LL, res);}TEST_METHOD(TestMethod4){auto res = Solution().Ans(998877665544332211LL);AssertEx(312742219398875473LL, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功