枚举

简述

顾名思义，枚举便是依次列举出所有可能产生的结果，根据题中的条件对所得的结果进行逐一的判断，过滤掉那些不符合要求的，保留那些符合要求的，也可以称之为暴力算法。

应用场合

在竞赛中，并不是所有问题都可以使用枚举算法来解决（事实上，只有少数），只有当问题的所有解的个数不太多时，并在我们题目中可以接受的时间内得到问题的解，才可以使用枚举。

例题

例题1

题意：输入一个正整数n，按从小到大的顺序输出形如a/b=n的表达式，其中100<=a<=999，2<=n<=79，且b必须是素数。
思路：a和n的范围都很小，我们可以使用枚举，代码如下：

#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;

bool check(int x)
{
    bool flag = true;
    for (int i = 2; i*i <= x; ++i) {
        if (x%i == 0) {
            flag = false;
            break;
        }
    }
    return flag;
}

int main()
{
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 100; i < 1000; ++i) {
            for (int j = 1; j < i; ++j) {
                if (check(j) && i%j == 0 && i/j == n) {
                    printf("%d/%d=%d\n", i, j, n);
                }
            }
        }
    }
    return 0;
}

例题2.hrbust 1565

题意：给出一个数字n(n<=1000000)请你计算出除了1和n之外n的因子数的个数。
要求：Time Limit: 1000 MS , Memory Limit: 10240 K
思路：首先我们通过分析n的范围和时限（1000ms）可以知道这道题可以使用枚举，我们可以通过枚举1到n中的每个整数，并判断该数是否是n的因子，使用一个count变量进行统计，时间复杂度是O(n)，代码如下：

int count=0;
for(int i=2;i<n;i++)
    if(n%i==0)
        count++;
printf("%d\n",count);

拓展：此题时限是1000ms，使用O(n)的算法可以过，如果把n的范围改成n<${10^{12}}$呢，O(n)的算法就会超时，那么应该怎么办？我们考虑这样一个规律：首先我们假设n是16，那么n的因子分别是1,2,4,8,16，我们可以得到这样一个规律：如果a是n的因子，那么n/a一定也是n的因子！所以我们可以将枚举的范围缩小到$[1,\sqrt n]$，这样我们可以把枚举的复杂度降低到O($\sqrt n$)。