素數篩
給定n, 求2~n內的所有素數
埃氏篩
利用素數的定義，
- 輸出素數2，然后篩掉2的倍數，得 {2,3,5,7,9,11,13，…}
- 輸出素數3，然后篩掉3的倍數，得 {2,3,5,7,11,13，…}
繼續上述步驟，直到隊列為空。
int E_sieve(int n) {vector<bool>fat(n+1,false);vector<int>tr(n);int s=0;for(int i=2;i<=sqrt(n);i++){ //篩選非負數if(!fat[i])for(int j=i*i;j<=n;j+=i) fat[j]=true; //標記為非素數}for(int i=2;i<=n;i++)if(!fat[i]) tr[s++]=i;return s;}
以【1,14】為例：
歐拉篩
歐拉篩是一種線性篩，是對埃氏篩的改進。
**原理：**一個合數肯定有一個最小質因數；讓每個合數只被它的最小質因數篩選一次。
- 逐次檢查2~n的所有數。第一個檢查的是2，他是第一個素數。
- 當檢查到第i個數時，利用求得的素數篩掉對應的合數x，而且是用x的最小質因數篩。
int prime[N];
int euler_sieve(int n){int cnt=0; //此時得到的素數數量bool vis[N];memset(vis,0,sizeof(vis));for(int i=2;i<=n;i++){ //i既在遍歷時判斷是否為素數，也充當篩選合數時的倍數。if(!vis[i]) prime[cnt++]=i;for(int j=0;j<cnt;j++){if(i*prime[j]>n) break; //只篩小于等于n的數vis[i*prime[j]]=1; //標記為篩除 循環中最少篩選1次，因為2是最小質數,合數的最小質因數>=2;if(i%prime[j]==0) break;//關鍵，此時下一個合數的最小質因數不是prime[j] 退出循環。//設i=prime[j]*t i*prime[j+1]=prime[j]*t*prime[j+1]//說明下一個i*prime[j]的最小質因數不是prime[j];}}}
以【1,15】為例：
雙子數
問題描述
若一個正整數能表示成（p2*q2）的形式（p，q為質數且互不相等）這稱這個數為雙子數，
求在[2333,2333333333333]范圍內有多少個雙子數？
原題鏈接
代碼
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll>dt;
void selve(ll n){ //歐拉篩，篩出所有平方*4小于23333333333333的質數unordered_set<ll>st; //記錄被篩除的數據int cnt=0;for(ll i=2;i<=n;i++){if(!st.count(i)) {dt.push_back(i);cnt++;}for(int j=0;j<cnt;j++){if(dt[j]*i>n) break;st.insert(dt[j]*i);if(i%dt[j]==0) break;}}
}
int main()
{// 請在此輸入您的代碼ll ans=0;ll t=sqrt(23333333333333/4);selve(t); //篩選出小于t的所有素數int i=0,j=dt.size()-1;while(i<=j){int k=i+1;while(dt[i]*dt[i]*dt[k]*dt[k]<2333) k++; //找下限while(dt[i]*dt[i]*dt[j]*dt[j]>23333333333333) j--; //找上限if(j>=k) ans+=(j-k+1); //dt[i]*dt[i]*dt[p]*dt[p]都滿足范圍約束，p屬于[k,j]; k，j為i固定下的最小值與最大值i++;}cout<<ans;return 0;
}
質數拆分
問題描述
將2019拆分成若干個兩兩不同的質數的和，共有多少種不同的方案數？
注：交換順序為同一種方案，如：2017+2=2019，與2+2017=2019為同種方案。
原題鏈接
代碼
#include <iostream>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
int sum=0;
int cnt=0;
int main()
{// 請在此輸入您的代碼vector<int>data;vector<bool>vis(2020);vector<long long>dp(2020);dp[0]=1;for(int i=2;i<=2019;i++){if(!vis[i]) {data.push_back(i);cnt++;}for(int j=0;j<cnt;j++){if(i*data[j]>2019) break;vis[i*data[j]]=true;if(i%data[j]==0) break;}} /*dp[i]表示若干個data中的元素相加為i的組合數。特殊地，dp[0]=1；*/for(int i=0;i<cnt;i++){ //遍歷ifor(int j=2019;j>=data[i];j--){ //每次以data[i]作為所選元素中最大值，確保不重復計算dp[j]+=dp[j-data[i]]; //更新若干個data元素相加為i的組合數}}cout<<dp[2019];return 0;
}
線性探測
求解前n個質數
前面的素數篩用于求解小于等于n的所有質數能在O(n)的時間復雜度內完成，那么求解前n個質數是否同樣有高效率呢？
答案是沒有，當求解前106個質數時，第106個質數大于10^7，復雜度約為O(10n)，往后相差更大。此時用試除探測的方法會更好。
代碼
vector<long long>d(1,2);
void sovle(int n){long long i=3; while(d.size()<n){int k=0;while(d[k]*d[k]<=i){if(i%d[k]==0){ //i是合數i+=2;k=1; //因為i是奇數，不用d[0]=2來試除。}else k++;}d.push_back(i); //i是質數i+=2; //偶數必定不是質數，每次加2，只探測奇數。}
}
分解因數
//質因數存儲在pa[]中
void zs(int n)
{for(int j=2;j<=n;j++)while(n%j==0){pa.push_back(j);n/=j;}
}
分解質因數的一個應用是求整數的正因數個數。
因數個數定理：大于1的整數n的約數個數等于n的每個質因數的冪（指數）加一的累乘
對 n 進行質因數分解： n = p 1 a 1 ? p 2 a 2 ? p 3 a 3 ? . . . ? p s a s ( p s 為 n 的質因數 ) 對n進行質因數分解： n=p_1^{a_1}*p_2^{a_2}*p_3^{a_3}*...*p_s^{a_s}(ps為n的質因數) 對n進行質因數分解：n=p1a1???p2a2???p3a3???...?psas??(ps為n的質因數)
n 的約數個數為 s u m = ∏ i = 1 s ( a i + 1 ) ; n的約數個數為 sum=\prod_{i=1}^{s}(a_i+1); n的約數個數為sum=i=1∏s?(ai?+1);
階乘約數
藍橋杯2020年國賽題
問題描述
求100！的約數個數。
原題鏈接
思路分析
前置知識：約數個數定理
因為任何一個正整數n都可以唯一分解為有限個素數的乘積，所以100！=p(1)*p(2)*p(3)*…p(100) p(x)為質因數分解式。
所以100！的因數個數為p(1)*p(2)*p(3)*…p(100) 中質因數的個數（指數）+1的累乘。
統計每個p（i）中質因數的個數 最后在算總的即可。
代碼
#include<bits/stdc++.h>
using namespace std;int a[101]={0};//存儲每個質數的個數 例a[2]=10 即質數2有10個（指數數為2）void zs(int n)
{for(int j=2;j<=n;j++)while(n%j==0){a[j]++;//若當前n中含有質數j,即將j存儲到a數組中n/=j;}
}int main()
{long long num=1;//num的范圍大for(int i=1;i<=100;i++)//統計每個質因數個數{zs(i);//可得當前數i含有的每個質數的個數}for(int i=1;i<=100;i++){if(a[i]!=0)num=num*(a[i]+1);//約數個數:等于它的質因數分解式中每個質因數的個數（即指數）加1的連乘的積。}cout<<num<<endl;return 0;
}
乘積尾0
問題描述
給定一個正整數數組，求數組中所有數相乘的結果末尾0的個數.
原題鏈接
思路分析
1.把每個數都拆成2的m次方乘以5的n次方再乘以一個常數的形式.該數的尾0數即為min（m,n)
2.所有拆分的數有a個2和b個5,那么會有min(a,b)個尾0.
統計所有數中的2的個數（指數）a 和5的個數（指數）b，最后結果就是min(a,b).
因為2和5互質，分解因數2不影響分解因數5.
代碼
int Zerosum(vector<int>&arr){int a=0,b=0;for(int i=0;i<arr.size();i++){int k=arr[i];while(k%2==0){ //分解因數2k/=2; a++; //因數2的指數+1}while(k%5==0){ //分解因數5k/=5;b++; //因數5的指數+1}}return min(a,b);
}
階乘尾零
將1*2*3*4*5*...*n當作一個整體看，只有5，10,15,20,25...含有因數5，定義這些乘數為因數5元子 且在整個階乘式子中每個相鄰的因數5元子中，都含有因數2元子與其配對。所以只需求因數5的個數即可。
原題鏈接
具體實現
代碼中 n/5求當前因數5元子的個數，再對n/=5(相當于對所有的因數5元子降冪一次),重新計算當前因數5元子的個數，這個過程可用遞歸進行。
目前最優
代碼
int trailingZeroes(int n) {return n==0?0:n/5+trailingZeroes(n/5);
}
丑數||
問題描述
給你一個整數 n ，請你找出并返回第 n 個 丑數 。
丑數 就是質因子只包含 2、3 和 5 的正整數。
原題鏈接
思路分析
任何一個數都能唯一進行質因數分解，一個丑數必能分解成（2 ^i * 3 ^ j * 5^k）的形式（i，j，k為自然數）。
每次將上一階段的丑數乘2或3或5，實現丑數的逐級遞增。
何時該乘2，何時乘3，何時乘5呢？
可以采用動態規劃，每次將上一階段求得的丑數儲存起來。當前階段的丑數，為上一階段的i，j，k指針對應的丑數分別乘2,3,5（分別記為num2,num3,num5）的最小值，同時讓最小值對應的指針后移一位（保證下次求最小值時不是同一個數，實現丑數逐級遞增）。
代碼
int nthUglyNumber(int n) {vector<int> dp(n + 1); //存儲前面計算結果dp[1] = 1;int p2 = 1, p3 = 1, p5 = 1; //p指針對應的是dp的下標for (int i = 2; i <= n; i++) {int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;dp[i] = min(min(num2, num3), num5); //取三者最小值if (dp[i] == num2) p2++;if (dp[i] == num3) p3++;if (dp[i] == num5) p5++;}return dp[n];}
比特位計數
問題描述
給你一個整數 n ，對于 0 <= i <= n 中的每個 i ，計算其二進制表示中 1 的個數 ，返回一個長度為 n + 1 的數組 ans 作為答案。
原題鏈接
思路分析
每個數不是是偶數就是奇數：
- 奇數，二進制表示中，奇數一定比前面那個偶數多一個最低位的 1。
- 二進制表示中，偶數中 1 的個數一定和右移一位之后的那個數一樣多。因為最低位是 0，右移一位就是把那個 0 抹掉而已，所以 1 的個數是不變的。
定義一個數組res，res[i]存儲了i的二進制表示的1的個數，從0到n枚舉，
枚舉到i是奇數res[i] = res[i >> 1] + 1；
枚舉到i是偶數res[i] = res[i >> 1] 。
代碼
vector<int> countBits(int n)
{vector<int> res(n + 1, 0);for (int i = 0; i <= n; i++){res[i] = res[i >> 1] + (i & 1);}return res;
}
分解質因數求單個歐拉函數
int euler(int n){int ans=n;for(int p=2;p*p<=n;p++){ //試除法if(n%p==0){ ans=ans/p*(p-1); //歐拉公式的通解while(n%p==0) n/=p; //去掉這個因數的冪，并使下一個p是質因數。}}if(n!=1) ans=ans/n*(n-1); //情況1，n是一個質數，沒有執行上面的分解return ans;
}
優質數對的總數
問題描述
給你兩個整數數組 nums1 和 nums2，長度分別為 n 和 m。同時給你一個正整數 k。
如果 nums1[i] 可以被 nums2[j] * k 整除，則稱數對 (i, j) 為 優質數對（0 <= i <= n - 1, 0 <= j <= m - 1）。
返回 優質數對 的總數。
原題鏈接
思路
為方便描述，把 nums1 和 nums2 簡記作 a 和 b。
a[i] 能被 b[j]?k 整除，等價于 a[i] 是 k 的倍數且 a[i]/k 能被 b[j] 整除。
也就是說，a[i]/k 有一個因子 d 等于 b[j]。
- 遍歷 a，枚舉 a[i]/k的所有因子，統計到哈希表 cnt 中。比如遍歷完后 cnt[3]=5，說明有 5 個 a[i]/k可以被 3 整除，等價于有 5 個 a[i] 可以被 3?k 整除。(因子為3的a[i]/k)有5個
- 遍歷 b，把 cnt[b[j]] 加入答案。例如 b[j]=3，那么就找到了 cnt[3] 個優質數對。
代碼
long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {unordered_map<int, int> cnt;for (int x : nums1) {if (x % k) {continue;}x /= k;for (int d = 1; d * d <= x; d++) { // 枚舉因子if (x % d) {continue;}cnt[d]++; // 統計因子if (d * d < x) {cnt[x / d]++; // 因子總是成對出現}}}long long ans = 0;for (int x : nums2) {ans += cnt.contains(x) ? cnt[x] : 0;}return ans;}
作者：靈茶山艾府
時間復雜度：O(n sqrt(U/k)+m)，其中 n 是 nums 1的長度，m 是 nums 2的長度，U=max(nums 1 )。
空間復雜度：O(U/k)。不同因子個數不會超過 U/k
將元素分配給組
問題描述
給你一個整數數組 groups，其中 groups[i] 表示第 i 組的大小。另給你一個整數數組 elements。
請你根據以下規則為每個組分配 一個 元素：
- 如果
groups[i]能被elements[j]整除，則元素j可以分配給組i。 - 如果有多個元素滿足條件，則分配下標最小的元素
j。 - 如果沒有元素滿足條件，則分配 -1 。
返回一個整數數組 assigned，其中 assigned[i] 是分配給組 i 的元素的索引，若無合適的元素，則為 -1。
**注意：**一個元素可以分配給多個組。
原題鏈接
思路分析
設 groups 中的最大值為 mx。我們直接預處理 1,2,3,…,mx 中的每個數能被哪個 elements[i] 整除。如果有多個相同的 elements[i]，只考慮最左邊的那個（i最小的那個）。
從左到右遍歷 elements，設 x=elements[i]。枚舉 x 的倍數 y（x，y都要小于mx），標記 y 可以被下標為 i 的元素整除，記作 target[y]=i。標記過的數字不再重復標記（保證獲取的i為最小的）。
?注意：如果我們之前遍歷過 x 的因子 d，那么不用枚舉 x 的倍數，因為這些數必然已被 d 標記。
最后，回答詢問，對于 groups[i]來說，答案為 target[groups[i]]。
初始 target所有元素都為?1。
代碼
vector<int> assignElements(vector<int>& groups, vector<int>& elements) {int mx = *max_element(groups.begin(),groups.end());vector<int> target(mx + 1, -1);for (int i = 0; i < elements.size(); i++) {int x = elements[i];if (x>mx||target[x] >= 0) { // x 及其倍數已被標記continue;}for (int y = x; y <= mx; y += x) { // 枚舉 x 的倍數 yif (target[y] < 0) {target[y] = i; // 標記 y 可以被 x 整除}}}// 回答詢問for (int& x : groups) {x = target[x]; // 原地修改}return groups;}
