2015
05-23

# Vampire Numbers

The number 1827 is an interesting number, because 1827=21*87, and all of the same digits appear on both sides of the ‘=’. The number 136948 has the same property: 136948=146*938.
Such numbers are called Vampire Numbers. More precisely, a number v is a Vampire Number if it has a pair of factors, a and b, where a*b=v, and together, a and b have exactly the same digits, in exactly the same quantities, as v. None of the numbers v, a or b can have leading zeros. The mathematical definition says that v should have an even number of digits and that a and b should have the same number of digits, but for the purposes of this problem, we’ll relax that requirement, and allow a and b to have differing numbers of digits, and v to have any number of digits. Here are some more examples:
126 = 6 * 21
10251 = 51 * 201
702189 = 9 * 78021
29632 = 32 * 926
Given a number X, find the smallest Vampire Number which is greater than or equal to X.

There will be several test cases in the input. Each test case will consist of a single line containing a single integer X (10 ≤ X ≤ 1,000,000). The input will end with a line with a single 0.

There will be several test cases in the input. Each test case will consist of a single line containing a single integer X (10 ≤ X ≤ 1,000,000). The input will end with a line with a single 0.

10
126
127
5000
0

126
126
153
6880

#include<iostream>
#include<cstdio>
#include<math.h>
using namespace std;

const int N=1100000;
int ans[N],num[10];

void func(int k,int c){
while(k){
num[k%10]+=c;
k/=10;
}
}

int check(int a,int b,int n){
memset(num,0,sizeof num);
func(a,1),func(b,1),func(n,-1);
for(int i=0;i<10;i++)
if(num[i]!=0) return 0;
return 1;
}

int isvp(int n){
int l=sqrt(1.0*n);
for(int i=2;i<=l;i++){
if(n%i!=0) continue;
if(check(i,n/i,n))	 return 1;
}
return 0;
}

int find(int n){
if(ans[n]!=0)//已经存在
return ans[n];
if(isvp(n))//是vp数
return ans[n]=n;
return ans[n]=find(n+1);//下一个vp数
}

int main(){
int n;
while(~scanf("%d",&n)&&n){
if(ans[n]==0)
find(n);
printf("%d\n",ans[n]);
}
return 0;
}