题目描述
枚举a->枚举C->算出b->检查是否符合->符合ans++
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 20;
int n;
bool st[N], backup[N];
int ans;
bool check(int a, int c)
{
int b = n * c - a * c;
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)
{
if(u == n) return;
if(check(a, c)) ans ++;
for (int i = 1; i <=9; i ++)
{
if(!st[i])
{
st[i] = true;
dfs_c(u + 1, a, c * 10 + i);
st[i] = false;
}
}
}
void dfs_a(int u, int a)
{
if (a >= n) return;
if (a) dfs_c(u, a, 0);
for(int i = 1; i <= 9; i++)
{
if(!st[i])
{
st[i] = true;
dfs_a(u + 1, a * 10 + i);
st[i] = false;
}
}
}
int main()
{
scanf("%d", &n);
dfs_a(0, 0);
printf("%d", ans);
return 0;
}