题解 | 排列式

链接

#include <bits/stdc++.h>

using namespace std ;
int cnt[10] ; //记录1-9数字出现的次数
struct node {
    int a , b , c ; // a = b * c 
    bool friend operator < (struct node A,struct node B) {
        return (A.a == B.a && A.b < B.b) || A.a < B.a ; //结果小的先输出结果相同乘数小的先输出
    }
};
int main() 
{
    /*
    有没有可能结果是5位数的可能
    如果len(ret) = 5 则 乘数是俩个长度加起来为4的 是不可能的
    因此结果长度是不可能大于5的
    有没有可能结果是3位数的可能
    如果len(ret) = 3 则 乘数是俩个长度加起来为6的因此不可能
    所以综上所述结果长度仅为4有解
    因此考虑乘数是俩个长度和为5的数
    */
    //假设俩个乘数一个是a 一个是b  那么方案去重后则枚举考虑a是1位和2位推出b即可
    //1.  a是个位数
    vector<node> ret; 
    for(int i = 1 ; i <= 9 ; i++) 
    {
        //则 b 是除 i 以外的8个数中选择4个数
        int a = i , b = 0 ;
        for(int b1 = 1 ; b1 <= 9 ; b1++)
            for(int b2 = 1 ; b2 <= 9 ; b2++) 
                for(int b3 = 1 ; b3 <= 9 ; b3++)
                    for(int b4 = 1 ; b4 <= 9 ; b4++)
                    {
                        memset(cnt , 0 , sizeof cnt) ;
                        cnt[i]++ , cnt[b1]++ , cnt[b2]++ , cnt[b3]++ , cnt[b4]++ ;
                        b = b1 * 1000 + b2 * 100 + b3 * 10 + b4 ;
                        int c = a * b ;
                        for(int j = c ; j ; j /= 10)
                            cnt[j%10]++ ;
                        bool flag = true ; //判断是否是合法
                        for(int j = 1 ; j <= 9 && flag ; j++) if ( cnt[j] != 1 ) flag = false ;
                        if ( flag && !cnt[0] ) ret.push_back({c,a,b}) ;
                    }
    }
    //2.  a是个俩位数
    for(int a1 = 1 ; a1 <= 9 ; a1++)
        for(int a2 = 1 ; a2 <= 9 ; a2++)
        {
            int a = a1 * 10 + a2 , b = 0 ;
            //则 b 是除a1、a2以外的7个数中选择3个数
            for(int b1 = 1 ; b1 <= 9 ; b1++)
                for(int b2 = 1 ; b2 <= 9 ; b2++) 
                    for(int b3 = 1 ; b3 <= 9 ; b3++)
                    {
                        memset(cnt , 0 , sizeof cnt) ;
                        cnt[a1]++ , cnt[a2]++ , cnt[b1]++ , cnt[b2]++ , cnt[b3]++ ;
                        b = b1 * 100 + b2 * 10 + b3 ;
                        int c = a * b ;
                        for(int j = c ; j ; j /= 10)
                            cnt[j%10]++ ;
                        bool flag = true ; //判断是否是合法
                        for(int j = 1 ; j <= 9 && flag ; j++) if ( cnt[j] != 1 ) flag = false ;
                        if ( flag && !cnt[0] ) ret.push_back({c,a,b}) ;
                    }
        }
    sort(ret.begin() , ret.end()) ;
    for(auto p : ret) 
    {
        cout << p.a << " = " << p.b << " x " << p.c << '\n' ;
    }
    
    
    return 0 ;
}