【Zoj 4061】Magic Multiplication

【题解】

```cpp /* for a[1] from 1~9 1*1=1 2*1=2 3*1=3 1*2=2 2*2=4 3*2=6 1*3=3 2*3=6 3*3=9 1*4=4 2*4=8 3*4=12 1*5=5 2*5=10 3*5=15 1*6=6 2*6=12 3*6=18 1*7=7 2*7=14 3*7=21 1*8=8 2*8=16 3*8=24 1*9=9 2*9=18 3*9=27 use "c[i]" or "c[i]c[i+1]" % a[1] if (c[i]%a[1]==0) then b[i] must be c[i]/a[1] else if (c[i]c[i+1]%a[i]==0) b[i] must be c[i]c[i+1]/a[1] they won't be true at the same time. Because,when x*y>=10,x*y%10 < x (1<=x,y<=9) so you won't confuse c[i] and c[i]c[i+1] if (c[i]c[i+1]%a[1]==0){ Scince c[i]c[i+1]>10 so,c[i]=c[i]c[i+1]%10=10 even though c[i]c[i+1]%a[1]==0 ```

【代码】

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5;

int n,m,l;
char s[N+10];
int a[N+10],b[N+10],c[N+10];

bool test(int a1){
 	a[1] = a1;

	//get string b                  
	int cur = 1;
	for (int i = 1;i <= m;i++){//for b's each position
		 if (cur>l) return false;
		 //break limit,unaccpted
		 if (c[cur]%a1==0){//only one position
		 	 b[i] = c[cur]/a1;//get b[i]
		 	 cur++;
		 }else if (cur+1<=l && (c[cur]*10+c[cur+1])%a1==0){//twoposition
			 b[i] = (c[cur]*10+c[cur+1])/a1;//get b[i]
			 if (b[i]>=10) return false;
			 cur+=2;
		 }else return false;//no accpted
	}


	//use b and c,get string a
	for (int i = 2;i <= n;i++){
	 	if (cur>l) return false;

	 	if (c[cur]%b[1]==0){
	 	 	a[i] = c[cur]/b[1];
	 	 	cur++;
	 	}else if (cur+1<=l && (c[cur]*10+c[cur+1])%b[1]==0) {
	 	 	a[i] = (c[cur]*10+c[cur+1])/b[1];
	 	 	if (a[i]>=10) return false;
	 	 	cur+=2;
	 	}else return false;

	 	//got a[i]

	 	//use a[i] to check c[cur],c[cur+1]....
	 	for (int j = 2;j <= m;j++){
	 		if (cur>l) return false;
	 	 	int _ju = a[i]*b[j];
	 	 	//if (a1==2) printf("%d
",_ju);
	 	 	if (_ju<=9 && c[cur]==_ju){
	 	 	 	cur++;
	 	 	}else if ( _ju>=10 && c[cur]==(_ju/10) && cur+1<=l && 
	 	 	c[cur+1]==(_ju%10) )  cur+=2;
	 	 		else return false; 
	 	}
	}
	//
	if (cur!=l+1) return false;
	return true;
}


int main(){
//	freopen("rush.txt","r",stdin);
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%d%d",&n,&m);		
		scanf("%s",s+1);
		l = strlen(s+1);
		for (int i = 1;i <= l;i++) c[i] = s[i]-'0';
		int ok = 0;
		for (int i = 1;i <= 9;i++)
			if (test(i)){
			 	ok = 1;
			 	break;
			}
		if (ok==0){
		 	puts("Impossible");
		}else{
		 	for (int i = 1;i <= n;i++) printf("%d",a[i]);printf(" ");
		 	for (int i = 1;i <= m;i++) printf("%d",b[i]);
		 	puts("");
		}
	}
 	return 0;
}