Description
Bipartite Number是这样的一个正整数，他只能由两段相同的数组成，如44444411,10000000, 5555556,41,而4444114,44444则不是。
现给你一个N，让你找到最小的Bipartite NumberX，使得X=NK(K是正整数，K>1)，由于答案X可能很大，你需将其缩写转换为4个数字输出，即(高位数字长度，高位数字，低位数字长度，低位数字)，如44444411为6 4 2 1，88888888888800000为12 8 5 0，N<=1e5，T<=20
从小到大枚举位数，再枚举最高位，用一个表动态记录%N=a的形如(10^c-1)/9*b（c<当前位数，1<=|b|<=9）的数中最小和次小的一个，以便枚举最低位的值查询是否可行
#include<cstdio>
#include<cstring>
int n,a1,a2,u1,u2,uu1,uu2;
int f[][][],ed[],tk=;
inline int fix(int x){return x+(x>>&n);}
void ins(int p1,int p2,int v){
if(ed[p1]!=tk){
ed[p1]=tk;
memset(f[p1],-,sizeof(f[p1]));
}
f[p1][p2][]=f[p1][p2][];
f[p1][p2][]=v;
}
int cal(int v1,int v2){
v2-=;
return (v2>?v1:-v1)*+v2;
}
void chk(int c1,int c2){
if(~c1&&(a1==-||cal(c1,c2)<cal(a1,a2)))a1=c1,a2=c2;
}
void find(int a,int b){
if(ed[a]==tk)chk(f[a][b][],b);
}
void findx(int a,int b,int c){
if(ed[a]==tk){
if(c==uu2){
if(f[a][b][]!=u2)chk(f[a][b][],b);
if(f[a][b][]!=u2)chk(f[a][b][],b);
}else chk(f[a][b][],b);
}
}
void chk(){
u1=-;
int ss[],sp=,p1,p2;
for(int x=n;x;ss[++sp]=x%,x/=);
for(p1=sp;p1>&&ss[p1]==ss[sp];--p1);
for(p2=p1-;p2>&&ss[p2]==ss[p1-];--p2);
if(p1&&!p2)u1=sp,u2=p1,uu1=ss[sp],uu2=ss[p1];
}
void cal(){
if(n==){
puts("1 1 1 0");
return;
}
++tk;
chk();
a1=-;
for(int i=,v=;;++i,v=(v*+)%n){
for(int a=,z=v;a<=;++a,z=fix(z+v-n)){
if(i==u1&&a==uu1){
for(int b=;b<=;++b)if(b!=a)findx(z,+b-a,b);
}else for(int b=;b<=;++b)if(b!=a)find(z,+b-a);
if(a1!=-){
printf("%d %d %d %d\n",i-a1,a,a1,a+a2-);
return;
}
}
for(int a=,z=v;a<=;++a,z=fix(z+v-n)){
ins(fix(-z),+a,i);
ins(z,-a,i);
}
}
}
int main(){
while(scanf("%d",&n)==&&n)cal();
return ;
}