神奇算式

欢迎访问我的新博客：http://www.milkcu.com/blog/

原文地址：http://www.milkcu.com/blog/archives/lanqiao-2014pa-3.html

原创：神奇算式 - 蓝桥杯

作者：MilkCu

摘要：本题是2014年第五届蓝桥杯全国软件大赛预赛A组第3题。

题目描述

标题：神奇算式

由4个不同的数字，组成的一个乘法算式，它们的乘积仍然由这4个数字组成。

比如：

210 x 6 = 1260 
8 x 473 = 3784
27 x 81 = 2187

都符合要求。

如果满足乘法交换律的算式算作同一种情况，那么，包含上边已列出的3种情况，一共有多少种满足要求的算式。

请填写该数字，通过浏览器提交答案，不要填写多余内容（例如：列出所有算式）。

解题思路

这个问题的思路也是枚举法，枚举对象分别为积和那个较小的乘数。

还有两个限制条件：

每个数字的每一位数字不允许重复；
这4个数字出现且仅出现2次。

这些限制条件是使用一个标记数组实现的。

代码实现

#include <iostream>
#include <cstring>
using namespace std;
int vis[10];
int bk[10];
int check(int x, int y) {
    do {
        if(vis[x % 10] == 0) {
            return 0;
        }
        vis[x % 10]--;
    } while(x /= 10);
    do {
        if(vis[y % 10] == 0) {
            return 0;
        }
        vis[y % 10]--;
    } while(y /= 10);
    return 1;
}
int check4(int x) {
    do {
        if(vis[x % 10] != 0) {
            return 0;
        }
        vis[x % 10]++;
    } while(x /= 10);
    return 1;
}
int main(void) {
    int cnt = 0;
    for(int i = 1023; i <= 9876; i++) {
        memset(vis, 0, sizeof(vis));
        if(!check4(i)) {
            continue;
        }
        memcpy(bk, vis, sizeof(bk));
        for(int j = 1; j <= 98; j++) {
            memcpy(vis, bk, sizeof(bk));
            if(i % j != 0) {
                continue;
            }
            int k = i / j;
            if(j > k) {
                continue;
            }
            if(!check(j, k)) {
                continue;
            }
            cout << j << " * " << k << " = " << i << endl;
            cnt++;
        }
    }
    cout << cnt << endl;
}

所有算式

6 * 201 = 1206
6 * 210 = 1260
21 * 60 = 1260
15 * 93 = 1395
35 * 41 = 1435
3 * 501 = 1503
3 * 510 = 1530
30 * 51 = 1530
21 * 87 = 1827
27 * 81 = 2187
9 * 351 = 3159
8 * 473 = 3784

最后答案

（全文完）

本文地址：http://www.milkcu.com/blog/archives/lanqiao-2014pa-3.html