當前位置：首頁 > 编程资源 > 综合教程 >内容正文

综合教程

基础枚举总结

發布時間：2023/12/3 综合教程 31 生活家

生活随笔收集整理的這篇文章主要介紹了基础枚举总结小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

基礎枚舉總結

前記：也是很基礎的一個專題了，大多數還是暴力可解，當然也有不行的，最難的部分用到了線段樹。。。從簡單做起，這種專題一天就能搞完，過兩天刷到難的專題，就不知道要多長時間才能刷完了。本專題持續更新。

文章目錄

基礎枚舉總結
- 【枚舉】桐桐的計算
- 【枚舉】桐桐去購物
- 【枚舉】打印算式
- 【枚舉】ISBN碼
- 【枚舉】格子位置
- 【枚舉】勾股數
- 【枚舉】桐桐的數學難題
- 【枚舉】因子個數
- 【枚舉】k個數乘
- 【因子游戲】因子游戲
- 【枚舉】素數的秘密
- 【枚舉】找數游戲
- 【枚舉】桐桐數
- 【枚舉】階乘因子
- 【枚舉】桐桐的思考
- 【枚舉】孿生素數
- 【枚舉】桐桐的猜想
- 【枚舉】統計素數
- 【枚舉】桐桐的研究
- 【枚舉】桐桐的深入研究
- 【枚舉】桐桐的游戲I
- 【枚舉】分數計算器
- 【枚舉】桐桐的砝碼
- 【枚舉】砝碼稱重
- 【枚舉】求組合數
- 【枚舉】燈的開關狀態

【枚舉】桐桐的計算

題目描述:
這個周末數學老師布置了一道有趣的題目，意思是：九頭鳥（傳說中的一種怪鳥，它有九個頭、兩只腳）、雞和兔子關在一個籠子里。數數它們的頭正好是100個，數數它們的腳也正好是100只。老師讓桐桐編程計算其中九頭鳥、雞和兔子各有多少只，你能幫助桐桐嗎？
輸入:
沒有輸入啦~
輸出:
前面若干行，每行輸出滿足題目條件的一個解，共三個數，分別表示九頭鳥、雞和兔子的只數，最后一行輸出題目解的總數。
雞兔同籠升級版，要是小學會編程，就不會被這玩意摧殘了。。。最基礎做法：3個for循環。

#include <stdio.h>
#define N 1000
int main()
{int x,y,z,i=0;for(x=0;x<=11;x++){for(y=0;y<=50;y++){for(z=0;z<=25;z++){if((9*x+y+z==100)&&(x+y+2*z==50)){printf("%d %d %d\n",x,y,z);i++;}}}}printf("%d\n",i);return 0;
}

【枚舉】桐桐去購物

題目描述:
桐桐周末陪媽媽到市場購物。她和媽媽來到一個買雞的攤位，發現雞的價格有三種：公雞每只5元錢，母雞每只3元錢，小雞3只1元錢。媽媽就給桐桐出了一道計算題：如果用n元錢買m只雞，問公雞、母雞和小雞可以各買多少只？注意：必須把n元錢正好用完，且買的各種雞的只數為大于等于0的整數。桐桐回到家里便拿起筆來認真計算，算了好久還沒得出答案。聰明的你通過編寫程序幫助桐桐找出結果好嗎？
輸入:
只有1行，兩個數n和m 0<n，m≤20000。
輸出:
有若干行，每行有三個數，分別為公雞、母雞和小雞的只數，用空格隔開，按照公雞只數升序排列。
賊基礎的題，但是總會謎之超時，TLE了幾次之后，又謎之AC。。。

#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
int main()
{double n=0;double m=0;cin>>n>>m;double i,j;if(n>0&&m<=20000){for(i=0; i<n/5; i++){for(j=0; j<m; j++){double k=m-i-j;if(5*i+3*j+k/3==n){cout<<i<<" "<<j<<" "<<k<<endl;}}}}return 0;
}

【枚舉】打印算式

題目描述:
設有下列的算式：

求出□中的數字，并打印出完整的算式來。
輸出:
除數靠當前行的最左邊，橫線的長度與被除數的長度相同，被除數、除數與“）”之間沒有空格。
注意格式，然后，就沒了。

#include<bits/stdc++.h>
using namespace std;
int main()
{int a,b,c,d,e;for (a=10; a<13; a++){c = 8*a;d = 9*a+1;e = 9*a;b = 100*c+d;if (b>=1000 && b<10000 && c<100 && e>=100 && e<1000){printf("    809\n");printf("   ----\n");printf("%d)%d\n",a,b);printf("   %d\n",c);printf("   ----\n");printf("    %d\n",d);printf("    %d\n",e);printf("   ----\n");printf("      1\n");}}return 0;
}

【枚舉】ISBN碼

題目描述:
Farmer John的奶牛們喜歡看書，并且Farmer John發現在他的奶牛們稍微看了些有關于自然科學的書時，會產出更多的牛奶。他決定更新牛棚里的圖書館，把原廉價的小說換成算術和數學的課本。不幸的是，有些新書掉到了泥漿里面，現在它們的ISBN號碼很難分辨出來了。
ISBN（國際標準圖書編號）是由十個阿拉伯數字組成的編碼，用來唯一地標識一本書。前九個阿拉伯數字描述這本書的一些信息，最后一個數字用來驗證ISBN碼是否正確。要驗證ISBN碼的正確性，你要把第一個數字乘以十，把第二個數字乘以九，把第三個數字乘以八……直到最后一個數字乘上一，再把這些積累加起來，如果所得的和可以被11整除的話，那么這就是一個合法的ISBN碼。比如說0201103311是一個合法的ISBN，因為
10×0+9×2+8×0+7×t+6×1+5×0+4×3+3×3+2×1+1×1=55
前九個數字都在0到9之間。有時候，最后一個數字需要取到10，那么我們就把最后一個數字寫成大寫X（這時就不叫數字了，呵呵），比如156881111X也是一個合法的ISBN碼。你的任務就是在給你丟失了一個數字的ISBN碼之后，確定那個丟失的數字。丟失數字的地方用“？”表示。
輸入:
一個十個數字組成的ISBN碼，其中包含用“？”表示的一個丟失的數字。
輸出:
就是那個丟失的數碼（0～9或大寫X）。如果標有“？”的位置上沒有數字可以使之成為一個合法的ISBN碼的話，就輸出-l。
樣例輸入
02011?3311
樣例輸出:
0
這種只有一組輸入的，最好輸出完直接return 0，要不然容易謎之WA。

#include<bits/stdc++.h>
using namespace std;
char a[15];
int main()
{scanf("%s", a);int ans = 0, v = 0;for (int i = 0; i < 10; i++){if(a[i] == 'X'){ans =ans+ 10;continue;}if(a[i] == '?')v = i;elseans =ans+(10 - i) * (a[i] - '0');}if(ans == 0){printf("-1\n");return 0;}int u = 0;for (int i = 0; i < 10; i++){if((ans + i * (10 - v)) % 11 == 0){printf("%d\n", i);u = 1;break;}}if(u==0){if((ans + 10) % 11 == 0 &&v == 9){printf("X\n");}else{printf("-1\n");}return 0;}return 0;
}

【枚舉】格子位置

題目描述:
輸入三個自然數N，i，j(l≤i≤N，1≤j≤N)，輸出在一個N×N格的棋盤中，與格子(i，j)同行、同列、同一對角線的所有格子的位置。例如，n=4，i=2，j=3表示棋盤中的第二行第三列的格子，如：n=4，i=2，j=3表示了棋盤中的第二行第三列的格子，如下圖：

當n=4，i=2，j=3時，輸出的結果是：
(2,1) (2,2) (2,3) (2,4) {同一行上格子的位置}
(1,3) (2,3) (3,3) (4,3) {同列列上格子的位置}
(1,2) (2,3) (3,4) {左上到右下對角線上的格子的位置}
(4,1) (3,2) (2,3) (1,4) {左下到右上對角線上的格子的位置}
輸入:
只有1行，共3個數，分別為N(1≤N≤10000)，i，j的值。
輸出:
按照題目描述的格式輸出。
樣例輸入:
4 2 3
樣例輸出:
(2,1)(2,2)(2,3)(2,4)
(1,3)(2,3)(3,3)(4,3)
(1,2)(2,3)(3,4)
(4,1)(3,2)(2,3)(1,4)
暴力求解，不會的面壁。

#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
int main()
{int n,i,j;scanf("%d%d%d",&n,&i,&j);for(int ii=1;ii<=n;ii++){printf("(%d,%d)",i,ii);}printf("\n");for(int ii=1;ii<=n;ii++){printf("(%d,%d)",ii,j);}printf("\n");int u=i,v=j;while(u&&v){u=u-1;v=v-1;}u++;v++;while(u<=n&&v<=n){printf("(%d,%d)",u,v);u++;v++;}printf("\n");u=i,v=j;while(u<=n&&v){u=u+1;v=v-1;}u--,v++;while(u&&v<=n){printf("(%d,%d)",u,v);u--,v++;}printf("\n");return 0;
}

【枚舉】勾股數

題目描述：
輸入整數R，輸出小于等于R的滿足X2+Y2=Z2的所有正整數X，Y，Z。
輸入：
只有一個數：R(5≤R≤1024)。
輸出：
只有一個數：表示共有多少組滿足條件的勾股數。
打表也行，但沒必要，直接三個for搞定。

#include <bits/stdc++.h>
using namespace std;
int main()
{int n,ans=0;scanf("%d",&n);for(int i=1;i<=1024;i++){for(int j=i+1;j<=1024;j++){for(int k=j+1;k<=1024;k++){if(i*i+j*j==k*k&&k<=n){ans++;}}}}printf("%d\n",ans);return 0;
}

【枚舉】桐桐的數學難題

題目描述：
今天數學課上，桐桐學習了質數的知識：一個正整數如果只能被1和它本身整除，那么這個整數便是質數。桐桐就想：任意一個正整數是否都能分解成若干個質數相乘的形式呢？輸入一個正整數n，把它分解成質因子相乘的形式，如果為質數則輸出該數本身。如：36=2×2×3×3；19=19。你能幫助桐桐解決這個難題嗎？
輸入：
輸入一個正整數n(2≤n≤1e9)
輸出：
把它分解成質因子相乘的形式，如果為質數則輸出該數本身，乘數從小到大輸出。
樣例輸入：
99
樣例輸出：
99=3311
這個蠻有意思的，說一下。需要求素數，我們有兩種選擇，歐拉篩和米勒羅賓素數定理，歐拉篩比較慢，但是準確，米勒羅賓快，但會有出錯率。由于1e9的數據，歐拉篩打不出來，所以博主采取了兩者并進的方式，大數用米勒羅賓，小數用歐拉篩，然后答案用STL里的隊列（queue，先進先出）存起來，最后再一個一個往出壓。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
//歐拉篩，v[n]為0，則n為素數
int a[1000005],v[1000005];
void getprime()
{int m=0;for(int i=2; i<=1000000; i++){a[m++]=i;for(int j=0; j<=m&&a[j]*i<=1000000; j++){v[i*a[j]]=1;if(i%a[j]==0)break;}}
}
//米勒羅賓，返回值為1則為素數
ll prime[6] = {2, 3, 5, 233, 331};
ll qmul(ll x, ll y, ll mod)
{return (x * y - (long long)(x / (long double)mod * y + 1e-3) *mod + mod) % mod;
}
ll qpow(ll a, ll n, ll mod)
{ll ret = 1;while(n){if(n & 1)ret = qmul(ret, a, mod);a = qmul(a, a, mod);n >>= 1;}return ret;
}
bool Miller_Rabin(ll p)
{if(p < 2)return 0;if(p != 2 && p % 2 == 0)return 0;ll s = p - 1;while(! (s & 1))s >>= 1;for(int i = 0; i < 5; ++i){if(p == prime[i])return 1;ll t = s, m = qpow(prime[i], s, p);while(t != p - 1 && m != 1 && m != p - 1){m = qmul(m, m, p);t <<= 1;}if(m != p - 1 && !(t & 1))return 0;}return 1;
}
int main()
{ll n;scanf("%lld",&n);if(Miller_Rabin(n)){printf("%lld=%lld\n",n,n);}else{queue<ll>que;ll m=n;while(!Miller_Rabin(n)){for(ll i=2; i<=n; i++){if(v[i]==0&&n%i==0){que.push(i);n=n/i;break;}}}printf("%lld=",m);while(!que.empty()){ll top=que.front();que.pop();printf("%lld*",top);}printf("%lld\n",n);}return 0;
}

【枚舉】因子個數

題目描述：
桐桐做完數學作業，閑來無事，她發現整數N的因子很有趣，好像還存在一些規律。她想把給定的整數N的因子個數計算出來，聰明的你能幫助她嗎？
輸入：
一個整數N(1≤N≤2000000000)。
輸出：
一個整數N的因子個數。
樣例輸入：
6
樣例輸出：
4
提示：
樣例說明：1、2、3、6共4個因子。
這個題就不掙扎了，直接米勒羅賓，暴力枚舉，從2到根號n，能除盡就+1。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll prime[6] = {2, 3, 5, 233, 331};
ll qmul(ll x, ll y, ll mod)
{return (x * y - (long long)(x / (long double)mod * y + 1e-3) *mod + mod) % mod;
}
ll qpow(ll a, ll n, ll mod)
{ll ret = 1;while(n){if(n & 1)ret = qmul(ret, a, mod);a = qmul(a, a, mod);n >>= 1;}return ret;
}
bool Miller_Rabin(ll p)
{if(p < 2)return 0;if(p != 2 && p % 2 == 0)return 0;ll s = p - 1;while(! (s & 1))s >>= 1;for(int i = 0; i < 5; ++i){if(p == prime[i])return 1;ll t = s, m = qpow(prime[i], s, p);while(t != p - 1 && m != 1 && m != p - 1){m = qmul(m, m, p);t <<= 1;}if(m != p - 1 && !(t & 1))return 0;}return 1;
}
int main()
{ll n;scanf("%lld",&n);int ans=2;if(Miller_Rabin(n)){printf("%d\n",ans);}else if(n==1){printf("1\n");}else{ans=0;int u=sqrt(n);for(int i=2;i<=u;i++){if(n%i==0){ans++;}}ans=ans*2+2;if(u*u==n)ans--;printf("%d\n",ans);}return 0;
}

【枚舉】k個數乘

題目描述:
桐桐想把一個自然數N分解成K個大于l的自然數相乘的形式，要求這K個數按從小到大排列，而且除了第K個數之外，前面(K-l)個數是N分解出來的最小自然數。例如：N=24，K=2時，輸出為24=2×12，而不是24=4×6；如N=3，K=I時，3=3; N=3，K=2時，輸出則為“No answer!”。你能幫助她嗎？
輸入:
第1行：N(2≤N≤107)；
第2行：K(1≤K≤100)。
輸出:
輸出樣例格式的分解式。
樣例輸入:
24
2
樣例輸出:
24=2*12
這題有個深淵巨坑，害我WA了好多發。。。除完之后要判斷最后一個數是不是1，如果是，還是要輸出“No answer!”的。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[5000005],v[5000005];
void getprime()
{int m=0;for(int i=2; i<=5000000; i++){a[m++]=i;for(int j=0; j<=m&&a[j]*i<=5000000; j++){v[i*a[j]]=1;if(i%a[j]==0)break;}}
}
ll prime[6] = {2, 3, 5, 233, 331};
ll qmul(ll x, ll y, ll mod)
{return (x * y - (long long)(x / (long double)mod * y + 1e-3) *mod + mod) % mod;
}
ll qpow(ll a, ll n, ll mod)
{ll ret = 1;while(n){if(n & 1)ret = qmul(ret, a, mod);a = qmul(a, a, mod);n >>= 1;}return ret;
}
bool Miller_Rabin(ll p)
{if(p < 2)return 0;if(p != 2 && p % 2 == 0)return 0;ll s = p - 1;while(! (s & 1))s >>= 1;for(int i = 0; i < 5; ++i){if(p == prime[i])return 1;ll t = s, m = qpow(prime[i], s, p);while(t != p - 1 && m != 1 && m != p - 1){m = qmul(m, m, p);t <<= 1;}if(m != p - 1 && !(t & 1))return 0;}return 1;
}
int main()
{getprime();ll n;scanf("%lld",&n);int k;scanf("%d",&k);if(k==1){printf("%lld=%lld\n",n,n);}else{ll m=n;queue<ll>que;if(Miller_Rabin(n))printf("No answer!\n");else{int flag=0;for(int i=2;i<n;i++){while(v[i]==0&&n%i==0){int u=que.size();if(u==k-1){flag=1;break;}que.push(i);n=n/i;}if(flag==1)break;}if(que.size()<k-1||n==1)//就是這里啦printf("No answer!\n");else{printf("%lld=",m);while(!que.empty()){ll top=que.front();printf("%lld*",top);que.pop();}printf("%lld\n",n);}}}return 0;
}

【因子游戲】因子游戲

題目描述：
桐桐把一個自然數N的正因子個數記為F(N)，例如18的所有正因子為1、2、3、6、9、18，所以F(18)=6。現在給出K，桐桐想求出所有滿足F(N)=K的N中最小的數，你能幫助她嗎？
輸入：
第1行為K，其中0<K≤80。
輸出：
如果存在不大于20000的解，則輸出這個N，并輸出相應的K個因子（行尾有一個空格）；否則輸出“NO SOLUTION”。
樣例輸入：
9
樣例輸出：
36
1 2 3 4 6 9 12 18 36
重點：數據<20000，此時不暴力，待何時？(注意下1和2的特判)

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{int n;scanf("%d",&n);if(n==1){printf("1\n");printf("1\n");}else if(n==2){printf("2\n");printf("1 2\n");}else{int flag=0,cnt=0;for(int i=2; i<=20000; i++){int ans=2;for(int j=2; j<=i/2; j++){if(i%j==0){ans++;}}if(ans==n){flag=1;cnt=i;break;}}if(flag==0){printf("NO SOLUTION\n");}else{printf("%d\n",cnt);printf("1 ");for(int j=2; j<=cnt/2; j++){if(cnt%j==0){printf("%d ",j);}}printf("%d\n",cnt);}}return 0;
}

【枚舉】素數的秘密

題目描述：
桐桐在上節分解質因數之后，對素數（質數）發生了興趣。大家都知道素數就是指只能被l和自身整除的數l例如2,3,5,7就是素數。桐桐想把不大于N的所有素數都輸出，你能幫助她解決這個問題嗎？
輸入：
一個正整數N（1<N≤40000)。
輸出：
輸出不大于N的所有素數，每行輸出5個素數。
樣例輸入：
2
樣例輸出：
2
數據小，歐拉篩即可，注意輸出格式。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[40005],v[40005];
void getprime()
{int m=0;for(int i=2;i<=40000;i++){a[m++]=i;for(int j=0;j<=m&&a[j]*i<=40000;j++){v[a[j]*i]=1;if(i%a[j]==0)break;}}
}
int main()
{getprime();int n;cin>>n;int k=1;int u=0;for(int i=n;i>=2;i--){if(v[i]==0){u=i;break;}}for(int i=2;i<=n;i++){if(v[i]==0){if(k==5){printf("%d\n",i);k=1;}else{if(u==i)printf("%d\n",i);elseprintf("%d ",i);k++;}}}return 0;
}

【枚舉】找數游戲

題目描述：
一個三位數，各位數字互不相同，十位數字比個位、百位數字之和還要大，且十位、百位數字之和不是質數。桐桐想把符合上述條件的三位數找出來，你能幫助她嗎？
輸入：
無
輸出：
按照從小到大的順序，每行輸出8個滿足條件的三位數，數與數之間有一個空格。
沒啥說的啊，還是歐拉篩暴力跑。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[40005],v[40005];
void getprime()
{int m=0;for(int i=2;i<=40000;i++){a[m++]=i;for(int j=0;j<=m&&a[j]*i<=40000;j++){v[a[j]*i]=1;if(i%a[j]==0)break;}}
}
int main()
{queue<int>que;getprime();for(int i=1;i<=9;i++){for(int j=0;j<=9;j++){for(int k=0;k<=9;k++){if(j>i+k&&v[i+j]==1&&i!=j&&i!=k&&j!=k){int t=100*i+10*j+k;que.push(t);}}}}int u=que.back();int k=1;while(!que.empty()){if(k==8){int p=que.front();que.pop();printf("%d\n",p);k=1;}else{int p=que.front();que.pop();if(u==p){printf("%d\n",p);}elseprintf("%d ",p);k++;}}return 0;
}

【枚舉】桐桐數

題目描述:
桐桐很喜歡研究數字，特別喜歡研究質數。一天，桐桐發現有一些數字可以表示成兩個質數相乘的形式，比如，10=2×5，2，5都是質數，所以10是一個“桐桐數”。所以桐桐決定考考你，她告訴你一個數n，請你判斷n是不是“桐桐數”。
輸入一個數n(1≤n≤2^31-1)。
輸出輸出一行，如果n是一個“桐桐數”，則輸出“It’s a Tongtong number.”，否則輸出“It’s not a Tongtong number.”
樣例輸入:
10
樣例輸出:
It’s a Tongtong number.
2^31-1正好是int的邊界，所以歐拉篩是沒那么大的，后面的枚舉也是暴力，不過到n/2就可以停了，畢竟再大沒意義。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll prime[6] = {2, 3, 5, 233, 331};
ll qmul(ll x, ll y, ll mod)
{return (x * y - (long long)(x / (long double)mod * y + 1e-3) *mod + mod) % mod;
}
ll qpow(ll a, ll n, ll mod)
{ll ret = 1;while(n){if(n & 1)ret = qmul(ret, a, mod);a = qmul(a, a, mod);n >>= 1;}return ret;
}
bool Miller_Rabin(ll p)
{if(p < 2)return 0;if(p != 2 && p % 2 == 0)return 0;ll s = p - 1;while(! (s & 1))s >>= 1;for(int i = 0; i < 5; ++i){if(p == prime[i])return 1;ll t = s, m = qpow(prime[i], s, p);while(t != p - 1 && m != 1 && m != p - 1){m = qmul(m, m, p);t <<= 1;}if(m != p - 1 && !(t & 1))return 0;}return 1;
}
int main()
{getprime();int n;scanf("%d",&n);int flag=0;for(int i=2;i<n/2;i++){int j;if(n%i==0){j=n/i;if(Miller_Rabin(i)&&Miller_Rabin(j)){flag=1;break;}}}if(flag==1){printf("It's a Tongtong number.\n");}elseprintf("It's not a Tongtong number.\n");return 0;
}

【枚舉】階乘因子

題目描述：
桐桐剛剛學習了自然數N的階乘：階乘(N!)被定義成從1到N的所有整數的乘積，例如5!=5×4×3×2×1=120。隨著數N的增大，N!增長得非常快，5!=120，10!=3628800。桐桐想到了一種方法來列舉那么大的數：不是直接列出該數，而是按照順序列舉出該數中各個質數因子出現的次數。如825可描述為(01201)，意思是對825分解質因數，這些質數因子中有0個2，1個3，2個5，0個7，1個11。請你編一個程序，讀入N值，幫助桐桐按順序輸出N!所包含的質數因子的個數。
輸入：
只包含1個數N(2≤N≤100000)。
輸出：
一個N!中所包含的質數因子的個數（從最小的質數開始）的序列，數與數之間用一個空格隔開。（注意：此題最后不需要輸出多余的回車和空格）
樣例輸入：
53
樣例輸出：
49 23 12 8 4 4 3 2 2 1 1 1 1 1 1 1
注意是階乘的因子。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize(2)
int prime[100100],ct=0,flag[100100];
int x;
int main()
{for(int i=2; i<=100000; i++){if(!flag[i])prime[ct++]=i;for(int j=0; j<ct&&prime[j]*i<=100000; j++){flag[prime[j]*i]=1;if(i%prime[j]==0)break;}}scanf("%d",&x);int fg=1;for(int j=0; j<ct&&prime[j]<=x; j++){int xz=prime[j];int ans=0;while(1){if(x/xz!=0)ans+=x/xz;elsebreak;xz=xz*prime[j];}if(fg==0)printf(" ");elsefg=0;printf("%d",ans);}return 0;
}

【枚舉】桐桐的思考

題目描述：
桐桐在學完了上節課的知識后，對信息學越發感興趣了。桐桐是一個很善于思考的學生，她發現上節課中例題的n最大是40000，如果數據再大一些，比如n=10^6，那么判斷素數的算法能否在1秒內給出答案呢？桐桐用程序實際測試的時間超過了1秒，你能幫助桐桐解決這個難題嗎？即：在1秒的時間內輸出不大于n (l
輸入：
一個正整數n(1<n≤106)。
輸出“
輸出不大于n的所有素數，每行輸出5個素數。
樣例輸入：
100
樣例輸出：
2 3 5 7 11
13 17 19 23 29
31 37 41 43 47
53 59 61 67 71
73 79 83 89 97
嘿嘿，看來我的算法還是不錯的，上一個那個數據為40000的題的代碼，我改了個數據，交上來還是AC。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[1000005],v[1000005];
void getprime()
{int m=0;for(int i=2;i<=1000000;i++){a[m++]=i;for(int j=0;j<=m&&a[j]*i<=1000000;j++){v[a[j]*i]=1;if(i%a[j]==0)break;}}
}
int main()
{getprime();int n;cin>>n;int k=1;int u=0;for(int i=n;i>=2;i--){if(v[i]==0){u=i;break;}}for(int i=2;i<=n;i++){if(v[i]==0){if(k==5){printf("%d\n",i);k=1;}else{if(u==i)printf("%d\n",i);elseprintf("%d ",i);k++;}}}return 0;
}

【枚舉】孿生素數

題目描述:
桐桐把大小之差不超過2的兩個素數稱為一對孿生素數，如2和3、3和5、17和19等等。請你幫助桐桐統計一下，在不大于自然數N的素數中，孿生素數的對數。
輸入:
一個自然數N(N≤10^6)。
輸出:
一個整數，表示N以內孿生素數的對數。
樣例輸入:
20
樣例輸出:
5
暴力枚舉。。。這題有點坑，百科上說相差為2的叫孿生素數，這題說不超過2就行，幸虧有樣例，要不然估計是要WA一次。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[1000005],v[1000005];
void getprime()
{int m=0;for(int i=2;i<=1000000;i++){a[m++]=i;for(int j=0;j<=m&&a[j]*i<=1000000;j++){v[a[j]*i]=1;if(i%a[j]==0)break;}}
}
int main()
{getprime();int n;cin>>n;int ans=0;for(int i=3;i<=n;i++){if((v[i]==0&&v[i-2]==0)||(v[i]==0&&v[i-1]==0))ans++;}printf("%d\n",ans);return 0;
}

【枚舉】桐桐的猜想

題目描述:
今天，桐桐在復習素數的知識時，發現了有趣的現象，例如4=2+2，5=2+3，6=3+3，7=2+5等等，桐桐列舉了很多數，都是這樣，所以她大膽地得出了一個結論：任何一個不小于4的數都能表示成兩個質數的和。你能找出一些反例，證明桐桐的結論是錯誤的嗎？
輸入:
第1行為一個整數n(1≤n≤50)；
接下來有n行，每行包含一個整數m (3≤m≤10^6)。
輸出:
共n行，每行對應于每一個m，如果m不能表示成兩個質數的和，則輸出“NO WAY!”；否則輸出一種方案。如果有多種可行方案，輸出兩個質數的差最大的那一種。
樣例輸入:
2
10
11
樣例輸出:
10=3+7
NO WAY!
枚舉到n/2，再不行就是沒有。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[3000005],v[3000005];
void getprime()
{int m=0;for(int i=2; i<=3000000; i++){a[m++]=i;for(int j=0; j<=m&&a[j]*i<=3000000; j++){v[a[j]*i]=1;if(i%a[j]==0)break;}}
}
int main()
{getprime();int t;scanf("%d",&t);while(t--){int n;int flag=0;scanf("%d",&n);for(int i=2; i<=n/2; i++){int j=n-i;if(v[i]==0&&v[j]==0){printf("%d=%d+%d\n",n,i,j);flag=1;break;}}if(flag==0)printf("NO WAY!\n");}return 0;
}

【枚舉】統計素數

題目描述：
桐桐想統計某個區間范圍里的素數，例如，A=2，B=10，則A和B之間（包括A、B）素數一共有4個，分別為：2，3，5，7。現在桐桐給出N個區間范圍，問每個區間有多少個素數。請你幫助她統計一下。
輸入：
第1行一個整數/N(1≤N≤10^5)；
后有N行，每行兩個整數A B(1≤A≤B≤10^6)，用空格隔開，表示一個區間范圍。
輸出：
共N行，每行一個整數，對應區間范圍的素數個數。
樣例輸入：
2
2 8
1 13
樣例輸出：
4
6
一個區間，這種題用線段樹妥妥的沒問題（線段樹要開4倍空間）。簡單介紹一下線段樹，線段樹是一種二叉樹，它的每一個節點代表一個區間[a，b]，它的葉節點代表單位區間[a,a]，即點a。
對一個非葉節點，設它的編號為x，區間為[a，b]，那么它的左兒子的編號就是（2x）,區間是[a,(a+b)/2]；它的右兒子的編號是（2x+1）,區間是[(a+b)/2+1,b]。
下面的build函數是建樹，l為左端點，r為右端點，rt一般在主函數里取1；update函數是更新（p點+v）;query函數是詢問，l1到r1的sum值，rt一般在主函數里取1。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[4000005],v[4000005];
void getprime()
{int m=0;for(int i=2; i<=4000000; i++){a[m++]=i;for(int j=0; j<=m&&a[j]*i<=4000000; j++){v[a[j]*i]=1;if(i%a[j]==0)break;}}
}
int sum[4000005];
//下面是線段樹模板
void build(int l,int r,int rt)
{if(r==l){if(l==1)sum[rt]=0;//1要特判else if(v[l]==0)sum[rt]=1;//是素數elsesum[rt]=0;//不是素數return;}int mid=(l+r)/2;build(l,mid,rt*2);build(mid+1,r,rt*2+1);sum[rt]=sum[rt*2]+sum[rt*2+1];
}
void update(int p,int v,int l,int r,int rt)
{if(r==l){sum[rt]+=v;return;}int mid=(l+r)/2;if(p<=mid)update(p,v,l,mid,rt*2);elseupdate(p,v,mid+1,r,rt*2+1);sum[rt]=sum[rt*2]+sum[rt*2+1];
}
int query(int l1, int r1, int l, int r, int rt)
{if(l1 <= l && r <= r1)return sum[rt];int mid = (l + r) / 2;int ret = 0;if (l1 <= mid)ret += query(l1, r1, l, mid,rt * 2);if (r1 > mid)ret += query(l1, r1, mid + 1, r, rt * 2 + 1);return ret;
}
int main()
{getprime();build(1,1000000,1);int t;scanf("%d",&t);while(t--){int a,b;scanf("%d%d",&a,&b);int u=query(a,b,1,1000000,1);printf("%d\n",u);}return 0;
}

【枚舉】桐桐的研究

題目描述：
在第一節桐桐已經接觸過因數（子），其實也就是約數：對于一個自然數n，如果存在一個非0的正整數d(d≤n)，使得n mod d=0，則d是n的約數。n=l時，約數只有一個為1，當n>l時，要分兩種情況：若n為質數，則其約數只有2個，即1和它本身；若n為非質數，則其約數個數肯定大于2個。顯然n的最大約數即為它本身。
桐桐對兩個自然數n和m的公約數發生了興趣，例如：n=8，m=36，它們的公約數有：1，2，4，其中最大的那個公約數4稱為這兩個自然數的最大公約數。
同時，兩個自然數n和m的公倍數也引起了桐桐的興趣：公倍數的概念與公約數類似，例如，n=8，m=36，它們的公倍數有：72，144，216，…，有無限多個，其中72是最小的公倍數，稱為這兩個自然數的最小公倍數。
請你編寫程序幫助桐桐求兩個自然數的最大公約數和最小公倍數。
輸入：
只有1行，為兩個自然數m，n(m≤10^8，n≤108)，用空格隔開。
輸出：
共2行，第1行為最大公約數，第2行為最小公倍數。
樣例輸入：
10 15
樣例輸出：
5
30
遞歸的寫一下gcd算法，然后，就沒了。。。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll gcd(ll x,ll y)
{if(y==0)return x;elsereturn gcd(y,x%y);
}
ll lcm(ll x,ll y)
{return x*y/gcd(x,y);
}
int main()
{ll n,m;cin>>n>>m;cout<<gcd(max(n,m),min(n,m))<<endl;cout<<lcm(max(n,m),min(n,m))<<endl;return 0;
}

【枚舉】桐桐的深入研究

題目描述:
兩個數的最大公約數與最小公倍數的問題解決了，桐桐又進行了進一步的研究。她發現求n個正整數的最大公約數與最小公倍數要復雜一些，你能幫助她解決這個問題嗎？
輸入:
第1行一個數n(2≤n≤100)，表示一共n個正整數；
第2行有n個正整數，相鄰的數用空格隔開，每個數不超過30000。
輸出:
第1行一個數，表示n個正整數的最大公約數；
第2行一個數，表示n個正整數的最小公倍數。
答案保證不超過長整型。
樣例輸入:
3
3 4 5
樣例輸出:
1
60
從大到小排個序，然后做法同上。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll gcd(ll x,ll y)
{ll a,b;a=max(x,y);b=min(x,y);x=a;y=b;if(y==0)return x;elsereturn gcd(y,x%y);
}
ll lcm(ll x,ll y)
{return x*y/gcd(x,y);
}
bool cmp(ll a,ll b)
{return a>b;
}
int main()
{ll n;ll a[105];cin>>n;for(int i=1;i<=n;i++){scanf("%I64d",&a[i]);}sort(a+1,a+1+n,cmp);int minn=gcd(a[1],a[2]);int maxn=lcm(a[1],a[2]);for(int i=3;i<=n;i++){minn=gcd(minn,a[i]);maxn=lcm(maxn,a[i]);}printf("%d\n",minn);printf("%d\n",maxn);return 0;
}

【枚舉】桐桐的游戲I

題目描述

桐桐正在和同桌吉吉玩一種數字游戲。游戲規則是這樣的：給定兩個正整數M和N，從桐桐開始，取其中較大的一個數，減去較小的數的正整數倍，當然，得到的數K不能小于0。然后是吉吉對剛才得到的數K和M、N中較小的那個數，再進行同樣的操作……直到一個人得到了O，他就取得了勝利。下面是他們用(25，7)兩個數游戲的過程。
初始：25 7
桐桐：11 7{18 7，11 7，4 7均可能）
吉吉：4 7
桐桐：4 3
吉吉：1 3
桐桐：1 0
桐桐取得了游戲的勝利。現在，假設他們都能夠“完美”地操作，誰會取得勝利呢？
輸入：
第1行只有一個數c(1≤C≤1000)，表示有C組測試數據；
下面有C行，每行有兩個正整數M和N，大小均不超過長整型。
輸出：
共有C行，每行輸出對當前組數據的游戲結果。如果桐桐勝利，則輸出“Tongtong wins”；否則輸出“Jiji wins”。
樣例輸入：
2
25 7
24 15
樣例輸出：
Tongtong wins
Jiji wins
這明明是個博弈的題，搞不懂為什么放到枚舉這。。。還好這博弈不難：大數只要是小數的兩倍及以上，那么這個人就具有主動權（可以直接拿到比小數小，也可以到小數的1倍和2倍之間，讓下一個人拿的情況固定），每次主動權，num++，最后num是奇數，桐桐贏，否則吉吉贏。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll minus1(ll a,ll b,ll num)
{ll c=max(a,b);ll d=min(a,b);while(d>0){num++;if(c/d>1)return num;else{ll e=c%d;c=d;d=e;}}return num;
}
int main()
{int t;scanf("%d",&t);while(t--){ll a,b;scanf("%I64d%I64d",&a,&b);ll num=0;num=minus1(a,b,0);if(num%2==0)printf("Jiji wins\n");elseprintf("Tongtong wins\n");}return 0;
}

【枚舉】分數計算器

題目描述:
Victor是一位很著名的科學家，在他的研究工作中經常要進行分數的運算。為了提高工作效率，Victor決定設計一個簡易的分數計算器，該計算器能夠進行分數的加、減、乘、除運算，并能將結果化為最簡分數和帶分數。
假設參加運算的分數都不是帶分數，并將整數看作分母為1的分數。你能發揮聰明才智，幫助Victor設計出這個分數計算器嗎？
(1)分數乘法法則可歸結為：
分數乘以分數，用分子相乘的積作分子，分母相乘的積作分母。

(2)分數除法法則可歸結為：
甲數除以乙數（0除外），等于甲數乘以乙數的倒數。例如：

輸入第一行：輸入第一個分數的分子和分母。
第二行：輸入運算符。
第三行：輸入第二個分數的分子和分母。
輸出:
以q/p的形式輸出運算結果的最簡分數；是假分數的還要化為帶分數，先輸出整數部分，再輸出后面部分。
樣例輸入:
9 1
/
4 11
樣例輸出:
24 3/4
唯一的問題是約分，用gcd就好了。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int gcd(int a,int b)
{if(b==0)return a;elsereturn gcd(b,a%b);
}
int main()
{int a,b;char ch;int c,d;cin>>a>>b;cin>>ch;cin>>c>>d;int e,f;if(ch=='*'){e=a*c;f=b*d;}else if(ch=='/'){e=a*d;f=b*c;}else if(ch=='+'){e=a*d+b*c;f=b*d;}else{e=a*d-b*c;f=b*d;}int u=gcd(max(e,f),min(e,f));e/=u;f/=u;int r=e/f;int yu=e%f;if(r>0)printf("%d ",r);printf("%d/%d\n",yu,f);return 0;
}

【枚舉】桐桐的砝碼

題目描述：
桐桐有2g、3g、5g、7g、10g、15g的砝碼各有一枚。她想知道用這些砝碼能稱出多少種不同的質量。
輸出：
只有一個數，表示能稱出的不同質量的個數。
這個題看著人畜無害，實際上還是有個坑的，要把0的情況減去。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int v[2000000]={0};
int main()
{int cnt=0;int a[2]= {0,2};int b[2]= {0,3};int c[2]= {0,5};int d[2]= {0,7};int e[2]= {0,10};int f[2]= {0,15};int num=0;for(int i=0; i<=1; i++){for(int j=0; j<=1; j++){for(int k=0; k<=1; k++){for(int s=0; s<=1; s++){for(int g=0; g<=1; g++){for(int h=0; h<=1; h++){int ans=a[i]+b[j]+c[k]+d[s]+e[g]+f[h];num++;if(v[ans]==0){v[ans]=1;cnt++;}}}}}}}cout<<cnt-1<<endl;return 0;
}

【枚舉】砝碼稱重

題目描述:
桐桐有1g、2g、3g、5g、10g、20g的砝碼各若干枚（其總質量≤1000）。她想知道用這些砝碼能稱出多少種不同的質量。
輸入:
只有1行：共6個數，分別為al，a2，a3，a4，a5，a6，表示1g砝碼有a1個，2g砝碼有a2個，．．．，20g砝碼有a6個，每種砝碼數量不超過10個。
輸出:
只有一個數：N，表示用這些砝碼能稱出的不同質量的個數，但不包括一個砝碼也不用的情況。
樣例輸入:
1 1 0 0 0 0
樣例輸出:
3
提示:
表示可以稱出1g，2g，3g三種不同的質量。
跟上題做法一樣。

#include<bits/stdc++.h>
#define maxn 220
#define INF 0x7f7f7f7f
using namespace std;
int main()
{int a1,a2,a3,a4,a5,a6;int sum=0;int u[1001]={0};cin>>a1>>a2>>a3>>a4>>a5>>a6;for(int i=0; i<=a1; i++){for(int i1=0; i1<=a2; i1++){for(int i2=0; i2<=a3; i2++){for(int i3=0; i3<=a4; i3++){for(int i4=0; i4<=a5; i4++){for(int i5=0; i5<=a6; i5++){int ans=i*1+i1*2+i2*3+i3*5+i4*10+i5*20;if(u[ans]==0){u[ans]=1;sum++;}}}}}}}cout<<sum-1<<endl;return 0;
}

【枚舉】求組合數

題目描述:
桐桐想找出n個自然數(1，2，3，…，n)中r個數的組合。例如，當n=5，r=3時，所有組合為：123 124 125 134 135 145 234 235 245 345，總共有10種組合。
輸入:
只有1行：兩個數n(1≤n≤30)和r(1≤r≤10)。
輸出:
共2行，第1行：滿足條件的所有組合，相鄰組合間用空格隔開；第2行：滿足條件的組合總數。
樣例輸入:
5 3
樣例輸出:
123 124 125 134 135 145 234 235 245 345
10
提示:
行末有空格
枚舉沒想出來咋解，搜索倒是可以，dfs暴力求解即可。

#include <bits/stdc++.h>
#define inf 1000000007
typedef long long ll;
using namespace std;
int n,r,ct=0;
int s[100],flag[100];
void dfs(int lj)
{if(lj==r+1){for(int i=1; i<=r; i++)printf("%d",s[i]);printf(" ");ct++;return;}for(int i=1; i<=n; i++){if(flag[i]||i<=s[lj-1])continue;s[lj]=i;flag[i]=1;dfs(lj+1);flag[i]=0;}
}
int main()
{scanf("%d%d",&n,&r);dfs(1);printf("\n");printf("%d\n",ct);return 0;
}

【枚舉】燈的開關狀態

題目描述：
有N個燈放在一排，從l到N依次順序編號。有N個人也從1到N依次編號。l號將燈全部關閉，2號將凡是2的倍數的燈打開；3號將凡是3的倍數的燈作相反處理（該燈如為打開的，則將它關閉；如關閉的，則將它打開）。以后的人都和3號一樣，將凡是自己編號倍數的燈作相反處理。
編程實現：第N個人操作后，按順序輸出燈的狀態（1表示燈打開，0表示燈關閉）。
輸入：
N(1≤N≤2000000)，燈的個數。
輸出：
燈的狀態，用01序列表示，中間無空格。
樣例輸入：
2
樣例輸出：
01
這題別想多，其實就是一倍一倍的往上加（之前記得有道題還要用唯一分解定理的，不過這個數據小，沒必要）。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int s[2000010];
int main()
{int n,i,j;scanf("%d",&n);memset(s,1,sizeof(s));for(i=1; i<=n; i++)for(j=i; j<=n; j+=i)s[j-1]=!s[j-1];for(i=0; i<n; i++)printf("%d",s[i]);printf("\n");return 0;
}

總結

以上是生活随笔為你收集整理的基础枚举总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

基础

上一篇： HDU1394(权值线段树)
下一篇： P2617 Dynamic Rankin