基礎(chǔ)數(shù)論應(yīng)用篇

• 子集和
• • 題目描述
• 篩質(zhì)數(shù)
• • 篩質(zhì)數(shù)模板
  • • 歐拉篩
    • 線性篩
  • 哥德巴赫猜想
  • 夏洛克和他的女朋友
  • 二次篩法
• 分解質(zhì)因數(shù)
• • 試除法分解質(zhì)因數(shù)
  • 分解階乘質(zhì)因子
• 快速冪
• • 模板
  • • 快速冪
  • 快速乘法
  • 序列的第k個數(shù)（模板練習(xí)）
  • 組合數(shù) + 快速冪
• 約數(shù)個數(shù)
• • 定理
  • 輕拍牛頭(約數(shù)個數(shù)轉(zhuǎn)為倍數(shù)思路)
  • 櫻花(約數(shù)個數(shù)+公式推導(dǎo))
  • 反素數(shù)(約數(shù)個數(shù)+數(shù)學(xué)知識)

子集和

題目描述

題目描述給你一個元素個數(shù)不超過30的整數(shù)集合，請你計算該集合所有子集的元素之和。例如集合{1，4}，則該集合的子集共四個{{空集}、{1}、{4}、{1、4}}，則子集的元素之和為1+4+1+4=10。輸入 第一行一個正整數(shù)n（1<=n<=30) 第二行n個大小在[1,1000000]范圍內(nèi)的正整數(shù)輸出 輸出給定集合所有子集的元素之和 樣例輸入 2 1 4 樣例輸出 10

題目思路及代碼
直接用結(jié)論元素之和乘以2的n-1次方。下面我們來講講為什么有這個結(jié)論:
我們依次考慮在每一個數(shù)在子集中出現(xiàn)的個數(shù):

篩質(zhì)數(shù)

篩質(zhì)數(shù)模板

歐拉篩

void init(){is_prime[0] = is_prime[1] = 1;for(int i = 2 ; i <= N ; ++i)if(!is_prime[i]){p[cnt++] = i;for(int j = i; j <= N/i ; j ++)is_prime[j*i] = 1;} }

線性篩

這里我要講一下線性篩的思路，因為在線性篩的時候有一些特殊的妙用。
即使在優(yōu)化后(從x2開始)， Eratosthenes 篩法仍然會重復(fù)標(biāo)記合數(shù)。例如12既會被2又會被3標(biāo)記，在標(biāo)記2的倍數(shù)時，12=62，在標(biāo)記3的倍數(shù)時，12=43。其根本原因是我們沒有確定出唯一的產(chǎn)生12的方式。
線性篩法通過“從大到小累積質(zhì)因子”的方式標(biāo)記每個合數(shù)，即讓12只有322一種產(chǎn)生方式。**設(shè)數(shù)組v記錄每個數(shù)的最小質(zhì)因子，**我們按照以下步驟維護(hù)v。1.依次考慮2~N之間的每一個數(shù)i。
2.若v[i]=i，說明i是質(zhì)數(shù)，把它保存下來。
3.掃描不大于v[i]的每個質(zhì)數(shù)p，令v[ip]=p。也就是在i的基礎(chǔ)上累積一個質(zhì)因子p。因為p≤v[i]，所以p就是合數(shù)ip的最小質(zhì)因子。

用處

• 篩素數(shù)
• 求每一個數(shù)的最小質(zhì)因子

代碼：

void pries(){is_prime[0] = is_prime[1] = 1;memset(v , 0 ,sizeof v); // 最小質(zhì)因子for(int i = 2 ; i <= N ; ++i){if(!is_prime[i]){v[i] = i ;p[++cnt] = i;}//給當(dāng)前的數(shù)i乘上一個質(zhì)因子for(int j = 1 ; j <= cnt ; ++j){//如果i有比p[j]更小的質(zhì)因子，或者超過N的范圍，停止循環(huán)if(p[j] > v[i] || p[j] > N/i)break;// p[j] 是合數(shù) i * p[j] 的最小質(zhì)因子v[i*p[j]] = p[j];}} }

哥德巴赫猜想

題目轉(zhuǎn)送門

解題思路:
本題我們在進(jìn)行素數(shù)篩之后，由到1e6 的質(zhì)數(shù)大約有1e5個，而本題是多組測試數(shù)據(jù)。因此對于每一個n，我們不能從頭或者開始找，而本題說了找的是差值最大的，因此我們可以前通過二分找到在質(zhì)數(shù)數(shù)組中第一個大于n的位置開始往后找。

同時雖然哥德巴赫猜想還沒有被證明出來，但目前還沒有反例，因此答案肯定是存在的。
代碼:

#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 1e6 + 10; int n; bool is_prime[N]; int cnt ,p[N] ,v[N];void init(){is_prime[0] = is_prime[1] = 1;for(int i = 2 ; i <= N ; ++i)if(!is_prime[i]){p[cnt++] = i;for(int j = i; j <= N/i ; j ++)is_prime[j*i] = 1;} }int main(){init();while(cin>>n,n)int pos = lower_bound(p , p + cnt , n) - p;for(int i = pos; i ; --i){if(p[i] < n && !is_prime[n - p[i]]){cout<<n << " = " << n - p[i] <<" + "<< p[i]<<endl;pos = i;break;}}return 0; }

夏洛克和他的女朋友

題目轉(zhuǎn)送門

解題思路:
這題很巧妙，同時我們注意條件使得一件珠寶的價格是另一件珠寶的價格的質(zhì)因子時，也就是說不相同的兩個另一個一定會質(zhì)數(shù)。那么如果我們將質(zhì)數(shù)都染成一種顏色，那么其余的合數(shù)都染成另外一種顏色即可。也就是最多需要兩個。這是因為質(zhì)數(shù)之間肯定是不符合條件的，在合數(shù)中，因為條件說了與其不相同的一定是質(zhì)數(shù)，因此也可以。

代碼：

#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 1e5 + 10; int n ; int is_prime[N] ,p[N]; int ans[N];void init(int n){for(int i = 2 ; i <= n ; ++i)if(!is_prime[i])for(int j = i ; j <= n / i ; ++j) is_prime[j*i] = 1; }int main(){cin>>n;init(n+1);bool flag;for(int i = 2 ; i <= n+1 ; ++i)if(!is_prime[i]) ans[i] = 1;else ans[i] = 2 ,flag = 1;if(flag )cout<<2<<endl;else cout<<1<<endl;for(int i = 2 ; i <= n + 1; ++i)cout<<ans[i]<<' ';return 0; }

二次篩法

題目轉(zhuǎn)送門

解題思路：

出處

因為題目說明左右兩端之間的數(shù)據(jù)不多與1e6，同時為了避免內(nèi)存爆炸。因此我們在進(jìn)行二次篩的時候是將值向左偏移L個單位，那么這樣最多只有1e6。

代碼：

#include<iostream> #include<algorithm> #include<cmath> #include<cstring> using namespace std; typedef long long LL; const int N = 1e7+10; int L,U ; int l ,r; bool st[N]; int cnt , prime[N];void init(int n){memset(st , 0 ,sizeof st);cnt = 0;for(int i = 2 ; i <= n ; ++i)if(!st[i]){prime[++cnt] = i;for(int j = i ; j <= n/i ; ++j)st[i*j] = 1;} }int main(){while(cin>>L>>U){init(50010);memset(st , 0 , sizeof st);for(int i = 1 ; i <= cnt ; ++i){LL p = prime[i];for(LL j = max(2*p , (L + p - 1)/p * p) ; j <= U ; j += p)st[j-L] = true; }cnt = 0;for(int i = 0 ; i <= U - L ; ++i)if(!st[i] && i + L >= 2)prime[cnt++] = i + L;if(cnt < 2) puts("There are no adjacent primes.");else{int minp = 0 , maxp = 0;for(int i = 0 ; i + 1 < cnt ; ++i){int d = prime[i+1] - prime[i];if(d < prime[minp+1] - prime[minp]) minp = i;if(d > prime[maxp+1] - prime[maxp]) maxp = i;}printf("%d,%d are closest, %d,%d are most distant.\n",prime[minp] ,prime[minp+1] ,prime[maxp] ,prime[maxp+1]);} }return 0; }

分解質(zhì)因數(shù)

試除法分解質(zhì)因數(shù)

分解質(zhì)因數(shù)：

枚舉1~sqrt(n)范圍內(nèi)的所有質(zhì)因子p（建一個素數(shù)表list），判斷 p是否是n的因子（能否整除）

① 如果是，那么給ans結(jié)果數(shù)組中增加p，并初始化其個數(shù)為0。然后，只要p還是n的因子，就不斷n除以p，每次操作令p的個數(shù)加1，直到p不是n的因子為止

② 如果不是，直接跳過
如果在上面的步驟結(jié)束后n仍然＞1，說明n有且僅有一個大于sqrt(n)的質(zhì)因子，這時需要把這個質(zhì)因子加入ans結(jié)果數(shù)組，令其個數(shù)為1
至此，ans數(shù)組中存放的就是質(zhì)因子分解的結(jié)果。

代碼:’

void get(int n ){for(int i = 2 ; i <= sqrt(n) ; ++i){if(n % i ){ans[++cnt] = i , c[cnt] = 0;while(n % i ) n /= i , c[cnt]++;}if( n > 1) ans[++cnt] = n , c[cnt]++; }

分解階乘質(zhì)因子

若把1~N每個數(shù)分別分解質(zhì)因數(shù)，再把結(jié)果合并，時間復(fù)雜度過高，為 O(N), 顯然，N!的每個質(zhì)因子都不會超過N，我們可以先篩選出1~N的每個質(zhì)數(shù)p，然后考慮階乘N!中一共包含多少個質(zhì)因子p。

N!中質(zhì)因子p的個數(shù)就等于$1?N$每個數(shù)包含質(zhì)因子p的個數(shù)之和。在1~N中，p的倍數(shù)，即至少包含1個質(zhì)因子p的顯然有 $[N/p]$ 個。而$p2$的倍數(shù)，即至少包含2個質(zhì)因子p的有 $[N/p^2]$個。不過其中的1個質(zhì)因子已經(jīng)在[N/p]里統(tǒng)計過，所以只需要再統(tǒng)計第2個質(zhì)因子，即累加上 $[N/p^2]$, 而不是 。2?$[N/p^2]$。 綜上所述，N!中質(zhì)因子p的個數(shù)為：
$\mid N/\rho \mid +\mid N/\rho 2\mid +\mid N/\rho 3\mid +?+\mid N/{\rho }^{\log pN}\mid$
對于每個p，只需要O(1gB)的時間計算上述和式。故對整個N!分解質(zhì)因數(shù)的時間復(fù)雜度為O(NlogN)。

在這里我們可以利用除法的思維來求解

這里隨帶講下

為什么在1~N中，p的倍數(shù)，即至少包含1個質(zhì)因子p的顯然有 $[N/p]$ 個：除法的本質(zhì) 。那么我們以 p = 2 的時候為例 ，我們 N / 2 下取整 ，就是得到最接近N的一個偶數(shù)（可以是自己，如果N是偶素的話），對其平均分，每一份有兩個的份數(shù)。那為什么這個份數(shù)是1`N中能被2整數(shù)的個數(shù)呢，假設(shè)份數(shù)為p ， 那么我們?nèi)〕鲆粋€得到2，取出2個得到4，… ，那么p份我們就可以通過取出1_{p份來得出1}N中能被2整除的所有數(shù)。

代碼：

// n！ 中質(zhì)因子p 個個數(shù) int get(int n , int p){int res = 0;for(LL i = p ; i <= n ; i *= p)res += n/i;return res; }

快速冪

模板

快速冪

至于快速冪的思路大家應(yīng)該很熟悉了。這里就細(xì)講一下。為什么這樣實現(xiàn)。b & 1得到最低位的1 ， b >>= 1可以去掉最低位的1. 我們知道快速冪是從小開始迭代起來的(底數(shù)跌打)。當(dāng)系數(shù)為1的時候表示我們需要乘當(dāng)前迭代到的值。至于系數(shù)是0的時候為1乘1沒有變化因此不用管。 同時還有一個重要原因是取余對于乘法有性質(zhì)。(a * b) % p =( ( a % p )* ( b % p )) % p

LL power(int a , int b){LL ans = 1 ;while(b){if(b & 1) ans = (LL) ans * a % mod;a = (LL)a * a%mod;b >>= 1;}return ans; }

快速乘法

我們有
$$a?b=a?c_i?b^{k?1}+a?c_j?b^{k?2}...+c_0?a?2^0$$由于加法對于取余也有與乘法類似的性質(zhì)。后一項與前一項的關(guān)系為$a?2^i=a?(2^{i?1})?2$

a * b LL mul(int a , int b){LL ans = 0;while(b){if(b & 1) ans = (LL)ans + a %mod;a = (LL) a * 2 % mod;b >>= 1;}return ans; }

序列的第k個數(shù)（模板練習(xí)）

對于等差數(shù)列第k項有 :$a_n=a_1+(k?1)?d$

對于等比數(shù)列第k項有 :$a_n=a_1?q^{k?1}$

代碼：

#include<iostream> #include<algorithm> using namespace std; const int mod = 200907;typedef long long LL;LL power(int a , int b){LL ans = 1 ;while(b){if(b & 1) ans = (LL) ans * a % mod;a = (LL)a * a%mod;b >>= 1;}return ans; }LL mul(int a , int b){LL ans = 0;while(b){if(b & 1) ans = (LL)ans + a %mod;a = (LL) a * 2 % mod;b >>= 1;}return ans; }int main(){int T;cin>>T;while(T--){int a ,b , c , k;cin>>a>>b>>c>>k;if(a + c == 2*b)cout<<( a + mul(b - a , k - 1)) % mod<<endl;elsecout<<(LL)a*power(b/a ,k - 1) % mod<<endl;}return 0; }

組合數(shù) + 快速冪

題目轉(zhuǎn)送門

解題思路：

同時對于結(jié)果，對于有一個額外的數(shù)乘上快速冪的結(jié)果我們需要對這個結(jié)果再來一次取模。對于相減可能得負(fù)數(shù)的情況，我們可以通過加mod 再取模解決；

代碼：

#include<iostream> #include<algorithm> using namespace std; const int mod = 100003 ;typedef long long LL; LL n , m ;LL power(LL a , LL b){LL ans = 1 % mod;while(b){if(b & 1) ans = (LL) ans * a % mod;a = (LL) a * a % mod;b >>= 1;}return ans ; }int main(){cin>>m>>n;cout<< ( power(m , n) - ((LL) m * power(m-1,n-1)) % mod + mod) % mod<<endl;return 0; }

約數(shù)個數(shù)

定理

這就是一個排列組合問題。我們知道p和c后，那么$p^n$一共能組成$p^0..p^n$一共(n+1）種數(shù)。其中的每一個數(shù)就能和其余p和c組成的 （m+1）中數(shù)組合成一個新約數(shù)。因此由乘法原理，方案數(shù)為上面式子。

輕拍牛頭(約數(shù)個數(shù)轉(zhuǎn)為倍數(shù)思路)

題目轉(zhuǎn)送門

解題思路:
這題問的是一個數(shù)，其余的數(shù)是其約數(shù)的個數(shù)(不包括自己)
在這里由于數(shù)據(jù)過大，因此我們不能通過求約數(shù)的方法來求。對于某一個值i ，我們令其倍數(shù)加上其出現(xiàn)的次數(shù)就可以了。這個看似是n^2復(fù)雜度，其實與求1-N的約數(shù)個數(shù)一樣，只是NlongN。

代碼：

#include<iostream> #include<algorithm> #include<cstdio> using namespace std; const int N = 1E6 + 10;int n; int cnt[N] , a[N] , s[N];int main(){cin>>n;for(int i = 1 ; i <= n ; ++i)scanf("%d",&a[i]) , cnt[a[i]]++;for(int i = 1 ; i <= N ; ++i)for(int j = 1 ; j <= N / i ; ++j)s[j*i] += cnt[i];for(int i = 1 ; i <= n ; ++i)printf("%d\n",s[a[i]] - 1);return 0; }

櫻花(約數(shù)個數(shù)+公式推導(dǎo))

題目轉(zhuǎn)送門

解題思路:
針對有兩個變量得式子，我們可以試著將其中一個變量寫成只含義另一個變量的形式。那么題目就轉(zhuǎn)變成了，后邊式子有多少種選法使得，y滿足條件。

對于這個題目，化簡有
$$y=\frac{x(n!)}{x?n!}$$

對x進(jìn)行變形，右分母的形式我們有
$$y=\frac{(x?n!+n!)(n!)}{x?n!}=n!+\frac{n{!}^2}{x?n!}$$
有y為正整數(shù)，n！也一定是正整數(shù)。那么這題就轉(zhuǎn)變?yōu)榱藊有多少種選法使得
$$\frac{n{!}^2}{x?n!}$$為正整數(shù)。能被$n{!}^2$整除的就是其約數(shù)，因為x取值為正整數(shù)集，因此分母的約數(shù)一定能表示出來。那么這題就變成了求$n{!}^2$中約數(shù)的個數(shù)。

我們對定理出發(fā)有

代碼:

#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 1E6 + 10 , mod = 1e9 + 7;int n ; int primes[N] , cnt; bool st[N];void init(int n ){for(int i = 2; i <= n ; ++i)if(!st[i]){primes[cnt++] = i;for(int j = 1 ; j <= n/i ; ++j) st[i*j] = 1;} }int get(int n , int p){int ans = 0;while(n){ans += n/p;n /= p;}return ans * 2; }int main(){cin>>n;int ans = 1;init(n);for(int i = 0 ; i < cnt && primes[i] <= n ; ++i)ans = (long long )ans * ( 1 + get(n , primes[i])) % mod;cout<<ans<<endl;return 0; }

反素數(shù)(約數(shù)個數(shù)+數(shù)學(xué)知識)

題目轉(zhuǎn)送門

解題思路:

引理一:1-N中最大的反質(zhì)數(shù)是1-N中約數(shù)最大的數(shù)中值最小的一個

引理二: 1~N中任何數(shù)的不同質(zhì)因子都不會超過10個。因為11個的話2*3…29 * 31 > 2 * 10^9 大于題目所給范圍。

引理三: x 為反質(zhì)數(shù)分必要條件是：x 可以分解為$$2^{c_1}?3^{c_2}....?39^{c_{10}},c_1>=c_2>=...>=c_{10}$$

綜上所述，我們可以使用深度優(yōu)先搜索(DFS)，嘗試依次確定前10個質(zhì)數(shù)的指數(shù)，并滿足指數(shù)單調(diào)遞減、總乘積不超過N，同時記錄約數(shù)的個數(shù)。
在這兩個限制條件下，搜索量實際上非常小。每當(dāng)搜索出一個滿足條件的整數(shù)時，我們就按照引理1的結(jié)論更新答案，最終得到約數(shù)個數(shù)最多的數(shù)中最小的一個。

代碼:

#include<iostream> #include<algorithm> #include<cstring> #include<cmath> using namespace std; const int N = 1E5; typedef unsigned long long LL; int n; LL maxn = 0, ans ; int primes[11] = {2,3,5,7,11,13,17,19,23,29};void dfs(int s ,LL sum , int p , LL cnt){if(sum > n)return ;if(p == 10 && sum <= n){if(cnt == maxn)ans = min(ans , sum);if(cnt > maxn) ans = sum;maxn = max(maxn ,cnt);return ;}if(s == 0 ) return ;for(int i = s ; i >= 0 ; --i)dfs(s,sum * (LL)pow(primes[p],i) , p+1 , cnt * (i+1));}int main(){cin>>n;ans = N;dfs(9,1,0 , 1);cout<<ans<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的算法之基础数论应用篇(一)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。