1209. 带分数 题解

#include <bits/stdc++.h>
using namespace std;
const int N = 15;

int n, ans;
bool st[N], backup[N];

bool check(int a, int c)
{
    long long b = n * (long long)c - a * c; //把公式整理一下，然后先把b计算出来
	if(!a || !b || !c)   return false;
	
	memcpy(backup, st, sizeof st); //因为我们要对这个判断是否出现的数组进行修改，但是原数组又不能变化，所以我们
    //额外开一个数组进行使用，这样就可以达到判断且不会改变原数组的目的
	
	while(b)
	{
		int x = b % 10; //取它的每一位，用来更新一下用过的数字
		b /= 10;  //删掉这个已经被选中的数
		if(!x || backup[x]) return false; 
		backup[x] = true;
	}
	
	for(int i = 1; i <= 9; i++) //遍历一下，判断每个数
		if(!backup[i])	return false;

	return true;
}

void dfs_c(int u, int a, int c) //u表示我们已经用了多少个数字
{
    if(u > 9)   return; //如果我们把10个数字都用了的话，那就直接return了
	if(check(a, c))	ans++; //如果满足要求，那我们判断一下a,c是否符合题目要求，如果符合，那么答案++
	 
	for(int i = 1; i <= 9; i++)  //否则的话我们把c从1到9全部枚举一遍
		if(!st[i]) 
		{
			st[i] = true;
			dfs_c(u + 1, a, c * 10 + i);  //如果这个数没用过，那么我们就把它放在c的后面,继续dfs下一层
			st[i] = false;
		}
}

void dfs_a(int u, int a)
{
	if(a >= n) 	return;
	if(a) dfs_c(u, a, 0);  //如果这个数没用过，那么我们就把它放在c的后面,继续dfs下一层
	
	for(int i = 1; i <= 9; i++)  //如果这个数没用过，那么我们就把它放在c的后面,继续dfs下一层
		if(!st[i]) 
		{
			st[i] = true;
			dfs_a(u + 1, a * 10 + i);  //如果这个数没有被用过，那么我们就加上它，并且dfs下一层
			st[i] = false;  //恢复现场，回溯一下
      }
		}
}

int main()
{
	cin >> n;
	
	dfs_a(0, 0); //第一个0表示我们已经用了多少个数字,后面那个0表示我们当前的a是多少
	
	cout << ans << endl;
	return 0;
}