HDU2840&&POJ2205 Self-Replicating Numbers 深搜

这题目HDOJ上过的人连100个都没有，所以不太敢直接暴力，后来学长们 暴力过了，不愧是学长，就是牛逼，然后学长告诉我 符合题目条件的数不多，所以可以暴力，倒不是因为题目数据水的缘故才能暴力的

题意：给你b,n，找出一个b进制的 长度为n的数， 这个数 它自身平方的得到的数 的后缀能与本身重合即可，举个例子

9376^2 = 79909376 ?

没有太多的想法，直接DFS暴力 字符串大数乘法就可以了，然后注意区分情况，我忽略了大于10进制的情况，结果浪费了两个小时的时间，其它也没啥了，还有输出排序

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>
#include<cctype>

#define ll long long
#define LL __int64
#define eps 1e-8

//const ll INF=9999999999999;

#define inf 0xfffffff

using namespace std;


//vector<pair<int,int> > G;
//typedef pair<int,int> P;
//vector<pair<int,int>> ::iterator iter;
//
//map<ll,int>mp;
//map<ll,int>::iterator p;

typedef struct Node {
	char s[2000 + 10];
};

Node sasd[2000 + 10];

int b,n;

int num[2000 + 10];

int tot;


void clear() {
	memset(num,sizeof(num));
	tot = 0;
}

void dfs(int pos,int e) {
	if(pos == n) {
		if(n != 1 && num[pos - 1] == 0)return;
		for(int i=pos - 1;i>=0;i--) {
			if(num[i] >= 10)
				sasd[tot].s[n - i - 1] = 'A' + num[i] - 10;//超过10进制的
			else 
				sasd[tot].s[n - i - 1] = '0' + num[i];
		}
		sasd[tot++].s[n] = 0;
		return;
	}
	for(int i=0;i<b;i++) {
		num[pos] = i;
		int ans = 0;
		for(int j=0;j<=pos;j++)
			ans += num[j] * num[pos - j];
		if((ans + e)%b == i)
			dfs(pos + 1,(ans + e)/b);
	}
}

bool cmp(Node x,Node y) {
	return strcmp(x.s,y.s) < 0;
}

int main() {
	while(scanf("%d %d",&b,&n) == 2) {
		clear();
		dfs(0,0);
		sort(sasd,sasd + tot,cmp);
		printf("%dn",tot);
		for(int i=0;i<tot;i++)
			printf("%sn",sasd[i].s);
	}
	return 0;
}