1

如果一個數 p 是個質數，同時又是整數 a 的約數，則 p 稱為 a 的一個質因數。
請問， 2024 的最大的質因數是多少？
答：23

---

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);//定義一個整數變量n，并將其初始值設為2024int n = 2024;//定義一個整數類型的向量f，用于存儲n的質因數vector<int> f;//從2開始遍歷到sqrt(n)，因為一個數的質因數不會超過它的平方根for (int i = 2; i * i <= n; i++) {//如果n能被i整除，說明i是n的一個質因數while (n % i == 0) {//將n除以i，繼續尋找n的其他質因數n /= i;//將找到的質因數i存入向量f中f.push_back(i);}}//如果經過上述步驟后，n仍然大于1，說明n本身是一個質數，將其存入向量f中if (n > 1) {f.push_back(n);}//對向量f進行升序排序sort(f.begin(), f.end());//將最大質因數輸出到標準輸出，并換行。cout << f.back() << '\n';//表示程序正常結束return 0;
}

• #include <bits/stdc++.h>：這是一個非標準的頭文件，它包含了幾乎所有標準庫的頭文件，使用它可以避免分別包含多個頭文件。
• using namespace std;：使用標準命名空間，這樣在代碼中就可以直接使用標準庫中的類和函數，而無需加上?std::?前綴。
• ios::sync_with_stdio(false);：關閉 C++ 標準輸入輸出流與 C 標準輸入輸出流的同步，這樣可以提高輸入輸出的效率。
• cin.tie(nullptr);：解除?cin?和?cout?的綁定，進一步提高輸入輸出的效率。
• sort?是 C++ 標準庫提供的一個強大的排序工具，在默認情況下它會按照升序對指定范圍內的元素進行排序。
• f.begin()：這是向量?f?的起始迭代器，它指向向量的第一個元素。迭代器可以理解為一種特殊的指針，用于遍歷容器中的元素。
• f.end()：這是向量?f?的末尾迭代器，它指向向量最后一個元素的下一個位置。

質因數分解的基本原理

質因數分解是將一個合數表示為若干個質數相乘的形式。例如，對于數字?12，它可以分解為2×2×3，其中2和3都是質數。在進行質因數分解時，我們需要從最小的質數2開始，依次檢查每個數是否是原數的因數。如果是，則將其作為一個質因數記錄下來，并將原數除以這個質因數，得到一個新的數，然后繼續對新的數進行分解，直到新的數為1為止

2

對于兩個整數a, b，既是a的整數倍又是b的整數倍的數稱為a和b的公倍數。公倍數中最小的正整數稱為a和b的最小公倍數。
請問，2024和1024的最小公倍數是多少？
答：259072

---

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);//定義兩個整數變量n和m，并分別初始化為2024和1024int n = 2024, m = 1024;cout << n / __gcd(n, m) * m << '\n';return 0;
}

• __gcd(n, m)：這是 GCC 編譯器提供的一個內置函數，用于計算?n?和?m?的最大公約數。在其他編譯器中，也可以使用?<numeric>?頭文件中的?std::gcd?函數來實現相同的功能。
• n / __gcd(n, m) * m：根據最大公約數和最小公倍數的關系：
  $$LCM(n,m)=\frac{n\times m}{GCD(n,m)}$$
  這里先將?n?除以?GCD(n, m)，再乘以?m，可以避免在計算??時可能出現的整數溢出問題。

#include <iostream>
#include <numeric>int main() {int n = 2024, m = 1024;std::cout << n / std::gcd(n, m) * m << '\n';return 0;
}

gcd最大公約數和?lcm最小公倍數

最大公約數GCD
最大公約數指的是兩個或多個整數共有約數中最大的一個。

最小公倍數LCM
最小公倍數是指兩個或多個整數公有的倍數中最小的一個。

3

如果一個數 p 是個質數，同時又是整數 a 的約數，則 p 稱為 a 的一個質因數。
請問， 2024 的所有質因數的和是多少？
答：40

---

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n = 2024;vector<int> f;for (int i = 2; i * i <= n; i++) {while (n % i == 0) {n /= i;f.push_back(i);}}if (n > 1) {f.push_back(n);}sort(f.begin(), f.end());//定義一個整數變量sum，用于存儲質因數的和，初始值為0int sum = 0;//使用范圍for循環遍歷向量f中的每個元素for (auto x : f) {//將每個質因數累加到sum中sum += x;}cout << sum << '\n';return 0;
}

范圍for

for (declaration : range) {// 循環體
}

• declaration：用于聲明一個變量，該變量將在每次循環迭代時依次綁定到?range?中的每個元素。
• range：表示要遍歷的對象，可以是數組、容器、初始化列表等可迭代對象。
• 循環體：每次迭代時執行的代碼塊。

4

請問，在不超過 2024 的數中，最大的質數是多少？
答：2017

---

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);//遞減循環，從2024開始，每次循環將i的值減1，直到找到質數為止for (int i = 2024;; i--) {//布爾變量flg，初始值為true，用于標記當前的i是否為質數bool flg = true;//將i的值賦給臨時變量t，避免在后續的判斷過程中修改i的值int t = i;//從2開始遍歷到，因為一個數的因數不會超過它的平方根for (int j = 2; j * j <= t; j++) {//如果t能被j整除，說明t不是質數，將flg置為false，并使用break語句跳出內層循環if (t % j == 0) {flg = false;break;}}//如果flg仍然為true，說明i是質數，將其輸出到標準輸出，并使用break語句跳出外層循環，結束程序if (flg) {cout << i << '\n';break;}}return 0;
}

5

如果兩個整數 a, b 除了 1 以外，沒有其它的公約數，則稱整數 a 與 b 互質。
請問，與 2024 互質的數中（包括1），第 2024 小的數是多少？
答：4655

---

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n = 2024;//定義一個整數變量cnt，用于記錄與n互質的數的個數，初始值為0int cnt = 0;//這是一個無限循環，從1開始逐個檢查整數ifor (int i = 1;; i++) {//使用__gcd函數計算i和n的最大公約數，如果最大公約數為1，則說明i和n互質if (__gcd(i, n) == 1) {//如果i與n互質，則將計數器cnt加1if (++cnt == 2024) {//當cnt達到2024，找到了第2024個與n互質的數，將其輸出并使用break語句跳出循環cout << i << '\n';break;}}}return 0;
}

6

對于字符串 S=ANQNANBNQNANQNQNBNINQNQNANQNINANQNANBNQNANQNQNBNBNQNQNANQNINANQNANBNQNANQNQNBNINQNQNANQNINBNQNANBNQN ，請找到S的一個長度不超過10的子串 A，使得（A的長度）乘以（A在S中出現的次數）最大。
請問這個子串是什么？（如果有多個滿足條件的，請回答字典序最小的）。
答：NQN

---

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);//定義一個字符串s，并初始化為給定的字符串string s = "ANQNANBNQNANQNQNBNINQNQNANQNINANQNANBNQNANQNQNBNBNQNQNANQNINANQNANBNQNANQNQNBNINQNQNANQNINBNQNANBNQN";//獲取字符串s的長度int n = s.size();//用于存儲最終結果的子串，初始為空string ans;//用于存儲最大的長度乘以出現次數的乘積，初始值為0int mx = 0;//外層循環枚舉子串的長度，從1到10for (int len = 1; len <= 10; len++) {//內層循環枚舉子串的起始位置，確保子串不會超出原字符串的范圍for (int i = 0; i + len - 1 < n; i++) {//使用substr函數提取從位置i開始、長度為len的子串string subs = s.substr(i, len);//用于記錄子串subs在原字符串中出現的次數，初始值為0int cnt = 0;//遍歷原字符串，檢查每個長度為len的子串是否與subs相等for (int j = 0; j + len - 1 < n; j++) {//如果相等，則將計數器cnt加1if (s.substr(j, len) == subs) {cnt += 1;}}//如果當前子串的長度乘以出現次數的乘積大于之前記錄的最大乘積，則更新最大乘積mx和結果子串ansif (len * cnt > mx) {mx = len * cnt;ans = subs;//如果乘積相等，但當前子串的字典序更小，則更新結果子串ans。} else if (len * cnt == mx && subs < ans) {ans = subs;}}}cout << ans << '\n';return 0;
}

for (int i = 0; i + len - 1 < n; i++)

• 初始化：int i = 0，定義一個整型變量?i?并將其初始值設為 0。i?表示子串在原字符串中的起始位置。
• 循環條件：i + len - 1 < n，這是決定循環是否繼續執行的條件。len?是當前正在考慮的子串的長度，n?是原字符串的長度。i + len - 1?表示子串的結束位置（因為數組下標從 0 開始）。這個條件確保子串不會超出原字符串的范圍。
• 迭代語句：i++，每次循環結束后，將?i?的值加 1，這樣就可以依次嘗試原字符串中不同位置作為子串的起始位置。

7

如果一個字符串中只包含字符0和字符1，則稱為一個01串（包含全為0的串和全為1的串）。
請問有多少個長度為24的01串，滿足任意5個連續的位置中不超過3個位置的值為1。

---

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);//定義一個整數變量n，并將其初始值設為24int n = 24;//使用位運算'1 << 24'計算的值，并將其輸出到標準輸出，然后換行cout << (1 << 24) << '\n';//定義一個整數變量ans，用于記錄滿足條件的二進制序列的數量，初始值為0int ans = 0;//使用位運算'1 << n'計算2^n的值，該循環會遍歷從0到2^n-1的所有整數，每個整數可以看作一個長度為n的二進制序列for (int i = 0; i < 1 << n; i++) {//定義一個長度為2的數組cnt，用于統計0和1的個數，初始值都為0int cnt[2] {};//遍歷二進制序列的前5位for (int j = 0; j < 5; j++) { // 0 .. 4//使用位運算`i >> j & 1`提取二進制序列中第`j`位的值（0 或 1），并將對應的計數器加1cnt[i >> j & 1] += 1;}//如果前5位中1的個數超過3個，則跳過當前二進制序列，繼續檢查下一個序列if (cnt[1] > 3) {continue;}//定義一個布爾變量ok，用于標記當前二進制序列是否滿足條件，初始值為truebool ok = true;//從第5位開始，依次檢查后續連續5位中1的個數for (int j = 5; j < n; j++) {//移除當前連續5位中最左邊的一位，并將對應的計數器減1cnt[i >> (j - 5) & 1] -= 1;//添加當前連續5位中最右邊的一位，并將對應的計數器加1cnt[i >> j & 1] += 1;//如果當前連續5位中1的個數超過3個，則將ok設為false，并跳出循環if (cnt[1] > 3) {ok = false;break;}}//如果ok為false，說明當前序列不滿足條件，跳過該序列，繼續檢查下一個序列if (!ok) {continue;//如果ok為true，說明當前二進制序列滿足條件，將ans加1} else {ans += 1;}}cout << ans << '\n';return 0;
}

1 << 24
位運算就是直接對整數的二進制位進行操作。<<?是左移運算符，它會將一個數的二進制表示向左移動指定的位數。
數字?1?的二進制表示是?0000 0000 0000 0000 0000 0000 0000 0001
移動后的二進制結果是?0001 0000 0000 0000 0000 0000 0000 0000

i >> j?是 C++ 中的右移運算符表達式
右移運算符：>>?是右移運算符，用于將一個整數的二進制表示向右移動指定的位數
對于表達式?i >> j，它會把整數?i?的二進制形式向右移動?j?位。

& 1?通常用于提取一個整數二進制表示的最低位（即最右邊的一位）。因為數字?1?的二進制表示在不同位數系統下，都是除了最低位為 1 其余位為 0
當一個整數與?1?進行按位與操作時，其他位都會因為和 0 進行按位與而變為 0，只有最低位會根據其自身的值（0 或 1）決定結果。如果最低位是 0，那么結果就是 0；如果最低位是 1，那么結果就是 1。