【数论】P8954 「VUSC」Math Game|普及+

本文涉及知识点

数论：质数、最大公约数、菲蜀定理

P8954 「VUSC」Math Game

题目背景

upd 2023.1.22：新增一组 Hack 数据 by @MCRS_lizi。

远在哞利坚的 Bessie 也要在新春之际走亲访友！为了打发时间，她常和 Farmer John 玩一个有趣的数字游戏。

题目描述

Farmer John 有一个集合 $S$，集合初始为 {2,3,4,...,N}\{2,3,4,...,N\}{2,3,4,...,N}。

对于两个在集合 $S$ 内的正整数 $p,q$，我们称它们为「一对好数」当且仅当 $p^k=q(k\ge 2\wedge k\in \mathbb{N})$。

我们将每个 $S$ 中的数看成一张无向图中的节点，对于每一对「好数」，我们在这两个数间连一条无向边。

Farmer John 会进行 $Q$ 次操作，操作有以下两种：

1. 给出 $x$，询问结点 $x$ 所在的连通块大小。
2. 给出 $x$，从 $S$ 中移除 $x$。与此同时，无向图中的结点 $x$ 也被移除。

由于 Bessie 的速度太慢了，她想要你来帮忙。

输入格式

第 $1$ 行 $2$ 个正整数，$N,Q$。

接下来 $Q$ 行，每行一个正整数，$o{p}_i,x_i$。
其中，$o{p}_i$ 表示操作的序号。

数据保证 $x_i$ 在集合 $S$ 中。

输出格式

对于操作 $1$，每行输出一个正整数，表示询问的答案。

输入输出样例 #1

输入 #1

30 6
1 6
1 4
2 9
1 3
2 2
1 16

输出 #1

1
4
2
2

说明/提示

【样例解释】

这是原始无向图（上面一排都是孤点）：

这是进行第一次操作 $2$ 后的无向图（删除了结点 $9$）：

这是进行第二次操作 $2$ 后的无向图（删除了结点 $2$）：

---

【数据范围】

全部数据满足：

• $2\le N\le 10^{18}$
• $1\le Q\le 10^6$
• $x_i\in S$
• opi∈{1,2}op_i \in \{1,2\}opi​∈{1,2}

测试点 $1\sim 2$ 另外满足 $2\le N\le 10^5$，$1\le Q\le 10^4$。

测试点 $3\sim 4$ 另外满足所有 $x_i=m^{p_i}$，其中 $m$ 为一满足 $m\ge 2\wedge m\in \mathbb{N}$ 的常数。

测试点 $5\sim 10$ 没有额外限制。

数论（暴力)

性质一：$q\ge 2\to p\ge 2$。
性质二：删点前，任何连通区域大小不超过60。$p\ge 2$则$p^{60}>10^{18}$，删点后并集查找只会变小。
性质三：删点前，某连通区域最小元素为y，则此连通区域所有元素都和y连通。用反证法证明：$y\leftrightarrow a\leftrightarrow b$，则$y\leftrightarrow b$，则$a=y^{k1},b=y^{k2}\to b=y^{k1\times k2}$
性质四： 删点后，最小元素不符合性质三。如：5删除。$5^2,5^3,5^6$是一个连通区域，但5^2和53不直接相连。
f(x)是x删点前所在连通区域的最小值。
利用唯一分解定理分解x，$x=\Pi p_i^{n_i},g=gcd(n)$。则f(x) =$\Pi p_i^{n_i}$

实现

用哈希集合记录所有删除的X。
预处理：v[i]记录i所有因数，包括1,不包括i。$1\le i\le 60$
查询X所在连通区域大小的算法如下：
一，求f(x)。
二，求最大K,$f(x{)}^K\le N$
三，k = 1 to K
如果 $f(x{)}^k$被删除，则忽略。
j : v[k]
如果$f(x{)}^j$未被删除，连通(i,j)。
令 x = $f(x{)}^{k1}$
g所在连通区域的大小就是答案。
时间复杂度：O($\sqrt{N}Q$)

稍稍加速

如果f(x)没有被删除，直接统计未被删除的数论。这样v[i]可以不包括1。

代码

#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 <bitset>
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 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();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 CUnionFind
{
public:CUnionFind(int iSize) :m_vNodeToRegion(iSize){for (int i = 0; i < iSize; i++){m_vNodeToRegion[i] = i;}m_iConnetRegionCount = iSize;}CUnionFind(vector<vector<int>>& vNeiBo) :CUnionFind(vNeiBo.size()){for (int i = 0; i < vNeiBo.size(); i++) {for (const auto& n : vNeiBo[i]) {Union(i, n);}}}int GetConnectRegionIndex(int iNode){int& iConnectNO = m_vNodeToRegion[iNode];if (iNode == iConnectNO){return iNode;}return iConnectNO = GetConnectRegionIndex(iConnectNO);}void Union(int iNode1, int iNode2){const int iConnectNO1 = GetConnectRegionIndex(iNode1);const int iConnectNO2 = GetConnectRegionIndex(iNode2);if (iConnectNO1 == iConnectNO2){return;}m_iConnetRegionCount--;if (iConnectNO1 > iConnectNO2){m_vNodeToRegion[iConnectNO1] = iConnectNO2;}else{m_vNodeToRegion[iConnectNO2] = iConnectNO1;}}bool IsConnect(int iNode1, int iNode2){return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);}int GetConnetRegionCount()const{return m_iConnetRegionCount;}//vector<int> GetNodeCountOfRegion()//各联通区域的节点数量//{//	const int iNodeSize = m_vNodeToRegion.size();//	vector<int> vRet(iNodeSize);//	for (int i = 0; i < iNodeSize; i++)//	{//		vRet[GetConnectRegionIndex(i)]++;//	}//	return vRet;//}std::unordered_map<int, vector<int>> GetNodeOfRegion(){std::unordered_map<int, vector<int>> ret;const int iNodeSize = m_vNodeToRegion.size();for (int i = 0; i < iNodeSize; i++){ret[GetConnectRegionIndex(i)].emplace_back(i);}return ret;}
private:vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引int m_iConnetRegionCount;
};template<class T = int>
class CUniqueFactorization
{
public:CUniqueFactorization(T iPrime, int cnt) {m_data.emplace_back(iPrime, cnt);}CUniqueFactorization(vector<T> primes = {}, vector<int> cnts = {}) {for (int i = 0; i < primes.size(); i++) {m_data.emplace_back(primes[i], cnts[i]);}}CUniqueFactorization operator+ (const CUniqueFactorization& o)const {return Add(o, true);}CUniqueFactorization Add(const CUniqueFactorization& o, bool bIgornZero = false)const {CUniqueFactorization ret;int i = 0, j = 0;while ((i < m_data.size()) && (j < o.m_data.size())) {if (m_data[i].first == o.m_data[j].first) {int cnt = m_data[i].second + o.m_data[j].second;if ((0 != cnt) || !bIgornZero){ret.m_data.emplace_back(m_data[i].first, cnt);}i++, j++;}else if (m_data[i].first < o.m_data[j].first) {ret.m_data.emplace_back(m_data[i]);i++;}else {ret.m_data.emplace_back(o.m_data[j]);j++;}}ret.m_data.insert(ret.m_data.end(), m_data.begin() + i, m_data.end());ret.m_data.insert(ret.m_data.end(), o.m_data.begin() + j, o.m_data.end());return ret;}CUniqueFactorization negation()const {CUniqueFactorization ret;ret = *this;for (auto& [i, cnt] : ret.m_data) {cnt *= -1;}return ret;}CUniqueFactorization GetValue(const CUniqueFactorization& o)const {CUniqueFactorization ret;for (const auto& [pri, cnt] : m_data) {ret.m_data.emplace_back(pri, 0);}return ret + o;};pair<T, T> Union()const {long long ll1 = 1, ll2 = 1;for (auto [pri, cnt] : m_data) {auto& ll = (cnt >= 0) ? ll1 : ll2;for (int j = 0; j < abs(cnt); j++) {ll *= pri;}//可以用快速指数幂加速}return { ll1,ll2 };}vector<pair<T, int>> m_data;
};class CCreatePrime {
public:CCreatePrime(int iMax) :m_isPrime(iMax + 1, true){m_isPrime[0] = m_isPrime[1] = false;for (int i = 2; i <= iMax; i++){if (m_isPrime[i]){m_vPrime.emplace_back(i);}for (const auto& n : m_vPrime){if ((long long)n * i > iMax) { break; }m_isPrime[n * i] = false;if (0 == i % n) { break; }}}}vector<int> m_vPrime;vector<bool> m_isPrime;
};
template<class T = int>
class CUniqueFactorizationFactory {
public:CUniqueFactorizationFactory(T iMax) :m_cc(sqrt(iMax) + 2), m_vPrime(m_cc.m_vPrime) {}CUniqueFactorization<T> Factorization(T x) {CUniqueFactorization<T> ret;for (const auto& iPre : m_vPrime) {int cnt = 0;while (0 == x % iPre) {cnt++;x /= iPre;}if (cnt > 0) {ret.m_data.emplace_back(iPre, cnt);}if (iPre * iPre > x) { break; }}if (x > 1) {ret.m_data.emplace_back(x, 1);}return ret;}const vector<int>& m_vPrime;
protected:CCreatePrime m_cc;
};class Solution {
public:vector<int> Ans(const long long N, vector<pair<int, long long>>& ope) {unordered_set<long long> sDel;vector<vector<int>> v(61, vector<int>(1, 1));for (int i = 2; i <= 60; i++) {for (int j = 2; (j < i); j++) {if (0 == i % j) { v[i].emplace_back(j); }}}CUniqueFactorizationFactory<long long> cff(1e7);auto f = [&](int x) {auto cf = cff.Factorization(x);int g = 0;for (const auto& [p, n] : cf.m_data) {g = gcd(g, n);}long long y = 1;for (const auto& [p, n] : cf.m_data) {for (int i = 1; i <= n / g; i++) {y *= p;}}return make_pair(y, g);};bool hasDel[61] = { 0 };vector<int>ans;auto Query = [&](long long x) {const auto [y, g] = f(x);auto tmp = y;int K = 1;hasDel[K] = sDel.count(tmp);for (; N / y >= tmp; ) {K++, tmp *= y;hasDel[K] = sDel.count(tmp);}CUnionFind uf(K + 1);for (int i = 2; i <= K; i++) {if (hasDel[i]) { continue; }for (const auto& j : v[i]) {if (hasDel[j]) { continue; }uf.Union(i, j);}}const int r = uf.GetConnectRegionIndex(g);ans.emplace_back(uf.GetNodeOfRegion()[r].size());};for (const auto& [kind, x] : ope) {if (1 == kind) {Query(x);}else {sDel.emplace(x);}}return ans;}
};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUGios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);	long long N;cin >> N;auto ope = Read<pair<int, long long>>();
#ifdef _DEBUGprintf("N=%d", N);//Out(xy, ",xy=");		//Out(edge, ",edge=");Out(ope, ",ope=");
#endif // DEBUGauto res = Solution().Ans(N, ope);for (const auto& s : res) {cout << s << "\n";}		return 0;
}

优化

$2==g$，直接y1=sqrt(x)，判断y1和y1+1的平方是否是x。如果不相信sqrt，可以手动二分。
vk[k] 升序记录所有k次方。直接lower,看是否相等。

代码

核心代码

#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 <bitset>
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 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();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 CUnionFind
{
public:CUnionFind(int iSize) :m_vNodeToRegion(iSize){for (int i = 0; i < iSize; i++){m_vNodeToRegion[i] = i;}m_iConnetRegionCount = iSize;}CUnionFind(vector<vector<int>>& vNeiBo) :CUnionFind(vNeiBo.size()){for (int i = 0; i < vNeiBo.size(); i++) {for (const auto& n : vNeiBo[i]) {Union(i, n);}}}int GetConnectRegionIndex(int iNode){int& iConnectNO = m_vNodeToRegion[iNode];if (iNode == iConnectNO){return iNode;}return iConnectNO = GetConnectRegionIndex(iConnectNO);}void Union(int iNode1, int iNode2){const int iConnectNO1 = GetConnectRegionIndex(iNode1);const int iConnectNO2 = GetConnectRegionIndex(iNode2);if (iConnectNO1 == iConnectNO2){return;}m_iConnetRegionCount--;if (iConnectNO1 > iConnectNO2){m_vNodeToRegion[iConnectNO1] = iConnectNO2;}else{m_vNodeToRegion[iConnectNO2] = iConnectNO1;}}bool IsConnect(int iNode1, int iNode2){return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);}int GetConnetRegionCount()const{return m_iConnetRegionCount;}//vector<int> GetNodeCountOfRegion()//各联通区域的节点数量//{//	const int iNodeSize = m_vNodeToRegion.size();//	vector<int> vRet(iNodeSize);//	for (int i = 0; i < iNodeSize; i++)//	{//		vRet[GetConnectRegionIndex(i)]++;//	}//	return vRet;//}std::unordered_map<int, vector<int>> GetNodeOfRegion(){std::unordered_map<int, vector<int>> ret;const int iNodeSize = m_vNodeToRegion.size();for (int i = 0; i < iNodeSize; i++){ret[GetConnectRegionIndex(i)].emplace_back(i);}return ret;}
private:vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引int m_iConnetRegionCount;
};class Solution {
public:vector<int> Ans(const long long N, vector<pair<int, long long>>& ope) {unordered_set<long long> sDel;vector<vector<int>> v(61, vector<int>(1, 1));for (int i = 2; i <= 60; i++) {for (int j = 2; (j < i); j++) {if (0 == i % j) { v[i].emplace_back(j); }}}static auto vk = InitVK();auto f = [&](const long long x) {for (int g = 60; g >= 3; g--) {auto it = lower_bound(vk[g].begin(), vk[g].end(), x);if ((vk[g].end() != it) && (x == *it)) {return make_pair((long long)(it - vk[g].begin() + 2), g);}}long long y1 = sqrt(x);if (y1 * y1 == x) { return  make_pair(y1, 2); }if ((y1 + 1) * (y1 + 1) == x) { return  make_pair(y1 + 1, 2); }return  make_pair(x, 1);};bool hasDel[61] = { 0 };vector<int>ans;auto Query = [&](long long x) {const auto [y, g] = f(x);auto tmp = y;int K = 1;hasDel[K] = sDel.count(tmp);for (; N / y >= tmp; ) {K++, tmp *= y;hasDel[K] = sDel.count(tmp);}CUnionFind uf(K + 1);for (int i = 2; i <= K; i++) {if (hasDel[i]) { continue; }for (const auto& j : v[i]) {if (hasDel[j]) { continue; }uf.Union(i, j);}}const int r = uf.GetConnectRegionIndex(g);ans.emplace_back(uf.GetNodeOfRegion()[r].size());};for (const auto& [kind, x] : ope) {if (1 == kind) {Query(x);}else {sDel.emplace(x);}}return ans;}vector<vector<long long>> InitVK() {vector<vector<long long>> vk(61);const long long llMax = 1e18;for (long long j = 2; ; j++) {const long long tmp = j * j * j;if (tmp > llMax) { break; }vk[3].emplace_back(tmp);}for (int k = 4; k <= 60; k++) {for (int i = 0; i < vk[k - 1].size(); i++) {if (llMax / (i + 2) < vk[k - 1][i]) { break; }vk[k].emplace_back(vk[k - 1][i] * (i + 2));}}return vk;}
};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUGios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);	long long N;cin >> N;auto ope = Read<pair<int, long long>>();
#ifdef _DEBUGprintf("N=%d", N);//Out(xy, ",xy=");		//Out(edge, ",edge=");Out(ope, ",ope=");
#endif // DEBUGauto res = Solution().Ans(N, ope);for (const auto& s : res) {cout << s << "\n";}		return 0;
}

单元测试

long long N;vector<pair<int, long long>> ope;TEST_METHOD(TestMethod1){N = 30, ope = { {1,6},{1,4},{2,9},{1,3},{2,2},{1,16} };auto res = Solution().Ans(N,ope);AssertV({ 1,4,2,2 }, res);}

扩展阅读

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

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。