ZR993

ZR993

首先,这种和平方有关的,首先应当考虑根号做法

这道题目,我们可以直接暴力(log_{10}w + 10)判断一个数是否能够由原数变化的到

直接(O(sqrt{n}))枚举所有的平方数,直接暴力上面的方法check

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<ctime>
#include<map>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 55;
const LL INF = 1e13;
LL n;
int s[N];
int num[11];
int num2[11];
int h[N];
inline LL read(){
	LL v = 0,c = 1;char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') c = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		v = v * 10 + ch - 48;
		ch = getchar();
	}
	return v * c;
}
inline bool work(LL x){
	memset(num2,0,sizeof(num2));
	if(x == 0) num2[0]++;
	while(x){
		num2[x % 10]++;
		x /= 10;	
	}
	for(int i = 0;i < 10;++i) if(num2[i] > num[i]) return 0;
	return 1;
}
int main(){
	n = read();
	while(n){
		memset(num,0,sizeof(num));
		LL g = n;int t = 0;
		while(g){
			h[++t] = g % 10; 
			num[g % 10]++;
			g /= 10;	
		}
		sort(h + 1,h + t + 1);
		LL to = 1;
		for(int i = t;i >= 1;--i) to = to * 10 + h[i]; 
		for(LL i = 0;1ll * i * i <= to;++i){
			if(work(i) && work(i * i))
				printf("%lld * %lld = %lld
",i,i,1ll * i * i);
		}
		n = read();	
	}
	return 0;	
}