题目描述

把一个整数n分解n=a+b/c的形式,a,b,c的每个数位都不同且式1-9的排列组合

样例

100

11

有用string的吗,用字符串切割函数substr分为三段a,b,c,然后用atoi转换为整型

有两个剪枝,一是b的位数一定大于c的位数,二是a的值一定小于n

#include<iostream>
#include<string>

using namespace std;

const int maxn = 10;
string st;
int ans, n;
int used[maxn];
void dfs(int u)
{
    if (u > 9)
    {
        for(int i=1;i<=8;++i){
            string sa = st.substr(1, i);
            int a = atoi(sa.c_str());
            if(a>n) continue;//a不可能大于n
            for (int j = i + 1; j <= 8; ++j) {
                if(j-i>=9-j){//b的位数要大于等于c的位数才能使b/c为整数
                string sb = st.substr(i+1, j - i), sc = st.substr(j + 1, 9-j);
                int b = atoi(sb.c_str()), c = atoi(sc.c_str());
                if (n*c == (a*c + b)) ++ans;
                }
            }
        }
        return;
    }
    for (int i = 1; i <= 9; ++i) {
        if (!used[i]) {
            used[i] = 1;
            st[u] = i + 48;
            dfs(u + 1);
            used[i] = 0;
        }
    }
}
int main()
{
    st.resize(10);
    cin >> n;
    dfs(1);

    cout << ans;

    return 0;
}