AcWing 1209. 带分数——小小暴搜,拿下!
原题链接
简单
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
int n;
bool st[N];
int path[N];
int num;
void dfs(int x)
{
if(x > 9)
{
//1 ~ 1 000 000
/*for(int i = 1; i <= 9; i ++)
printf("%d", path[i]);
puts("");*/
int a = 0;
//123 456 789
for(int i = 1; i <= 7; i ++)
{
a = a * 10 + path[i];
if(a >= n) break;
int b = 0;
for(int j = i + 1; j < 9; j ++)
{
b = b * 10 + path[j];
int c = 0;
for(int k = j + 1; k <= 9; k ++)
c = c * 10 + path[k];
if(b < c || b % c != 0 || a + b/c != n) continue;
num ++;
}
}
return;
}
for(int i = 1; i <= 9; i ++)
{
if(st[i] == 0)
{
path[x] = i;
st[i] = 1;
dfs(x + 1);
st[i] = 0;
}
}
}
int main()
{
cin >> n;
dfs(1);
cout << num << endl;
return 0;
}