算法1

(搜索)

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=1e3,M=4e5;

int n;
int st[13],temp[12];
int res,st1[M][5],len;

int merge1(int l,int r)
{
    int sum=0;
    for(int i=l;i<=r;i++) sum=sum*10+temp[i];
    return sum;
}



void dfs(int t)
{
    if(t>9)
    {
        for(int i=1;i<=7;i++)//最多前7位
        {
        int t=merge1(1,i);//合并
        if(t>n) break;//如果前几位合并后超过n则直接break
        for(int j=i+1;j<=8;j++)//最多使用2~8位
        {
            int t1=merge1(i+1,j),t2=merge1(j+1,9);
            if(t1%t2==0&&t+t1/t2==n) 
                res++;

        }
        }

        return ;
    }

    for(int i=1;i<=9;i++)//枚举全排列
    {
        if(!st[i])
        {
            st[i]=1;
            temp[t]=i;
            dfs(t+1);
            temp[t]=0;
            st[i]=0;
        }
    }

}

int main()
{
    cin>>n;
    dfs(1);

    cout<<res;
    return 0;
}