2018ICPC青岛站 D . Magic Multiplication（构造 模拟）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;typedef unsigned long long ull;
typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD;
#define I_int ll
inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
#define read read()
#define rep(i, a, b) for(int i=(a);i<=(b);++i)
#define dep(i, a, b) for(int i=(a);i>=(b);--i)
ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
const int maxn=4e5+7,maxm=1e6+7,mod=1e9+7;
int n,m,pos=0,len;
int a[maxn],b[maxn],c[maxn];
int pa=0,pb=0,pc=0;
int ans_a[maxn],ans_b[maxn];
int getb(int x){//a[1]=x
    pb=0;
    int idx=0;
    while(pos<len&&idx<m){
        int now=c[pos];
        if(now>=x){
            if(now%x) return 0;
            b[idx]=now/x;
            idx++;
        }
        else{
            if(pos==len-1&&now!=0) return -100;
            if(now!=0) now=now*10+c[++pos];
            if(now%x) return 0;
            b[idx]=now/x;
            idx++;
        }
        pos++;
    }
    pb=idx;
  //  cout<<idx<<" "<<m<<" "<<pos<<" "<<len<<endl;
    if(idx==m) return 1;
    return 0;
}
int geta(int x){
  pa=1;
  a[0]=x;
    int bf=b[0];
  while(pos<len&&pa<n){
    int now=c[pos];
    int ta=0;
    if(now>=bf){
      if(now%bf) return 0;
      a[pa]=now/bf;
      ta=now/bf;
      pa++;
    }
    else{
      if(pos+1==len&&now!=0) return 0;
      if(now!=0) now=now*10+c[++pos];
      if(now%bf) return 0;
      a[pa]=now/bf;
      ta=now/bf;
      pa++;
    }
    pos++;
    for(int i=1;i<m;i++){
      int tb=b[i];
      int num=ta*tb;
      int now=c[pos];
      if(num>=10){
        if(pos==len-1) return 0; 
        now=now*10+(c[++pos]);
        if(num!=now) return 0;
      }
      else{
        if(num!=now) return 0;
      }
      pos++;
    }
  }
  //cout<<pos<<"**"<<len<<endl;
  if(pa!=n||pos!=len) return -5;
  return 1;
}
int main(){
    int _=read;
    while(_--){
        n=read,m=read;
        string s;cin>>s;
        len=s.size();
        pos=0;
        for(int i=0;i<len;i++){
          c[i]=s[i]-'0';
        }
        pa=pb=pc=0;
        bool flag=0;
        for(int i=1;i<=9;i++){
          pos=0;
          int ff=getb(i);
            /*if(i==1){
              cout<<ff<<endl;
              for(int i=0;i<m;i++) cout<<b[i];
              puts("");
            }*/
            if(ff==1){
                int f=geta(i);
                /*if(i==1){
                  cout<<f<<endl;
                  for(int i=0;i<n;i++) cout<<a[i];
                puts("");
                }*/
                if(f==1){
                    for(int i=0;i<n;i++) ans_a[i]=a[i];
                    for(int i=0;i<m;i++) ans_b[i]=b[i];
                    flag=1;
                    break;
                }
            }
        }
       // cout<<flag<<endl;
        if(flag){
          rep(i,0,n-1) printf("%d",ans_a[i]);
          printf(" ");
          rep(i,0,m-1) printf("%d",ans_b[i]);
          puts("");
        }
        else puts("Impossible");
    }
    return 0;
}
/*
1
2 2
8101215
*/