文章目录

[D - Magic Multiplication ](https://zoj.pintia.cn/problem-sets/91827364500/problems/91827370311)题目大意解题思路代码

D - Magic Multiplication

题目大意

一共有T组数据，每次给你一个n，一个m和一个字符串s，表示一个n位数和一个m位数按照指定的规则运算结果是s，问你有没有这样的两个数存在，如果存在输出最小的n位数和m位数。

解题思路

看上去数据很大，但是仔细看的话，你会发现存在的可能新很少。完全可以直接模拟然后加上剪枝就可以了。

代码

#include<bits/stdc++.h> using namespace std; #define ll long long const ll mod=1000000007; const int mx=200100; int n,m,len; int a[mx],b[mx]; string s; int pos; bool getb(){ int now; for(int i=0;i<m;i++){ now=s[pos++]-'0'; // 如果不能整除就加上 下一位看看 if(now%a[0]!=0){ now=now*10+s[pos++]-'0'; } //如果可以整除且结果小于10 就可以赋值，大于 //10就是二位数，一位放不下所以不行 if(now%a[0]==0&&now/a[0]<10){ b[i]=now/a[0]; }else return 0; } return 1; } bool geta(){ for(int i=1;i<n;i++){ int now=s[pos++]-'0'; if(now%b[0]!=0) now=now*10+s[pos++]-'0'; if(now%b[0]==0&&now/b[0]<10){ a[i]=now/b[0]; }else return 0; //判断 b 的时候不能取模是因为 a的位置有可能为零 // 会RE for(int j=1,x;j<m;j++){ now=s[pos++]-'0'; if(now<b[j]&&now!=0) now=now*10+s[pos++]-'0'; // 如果不等就不行 if(a[i]*b[j]!=now){ return 0; } } } return 1; } bool check(){ // 分两种情况乘完进位了，和不进位 int one=s[0]-'0'; int two=one*10+s[1]-'0'; for(int i=1;i<10;i++){ pos=0; //只要能整除就可以试试 if(one%i==0){ a[0]=i; if(getb()&&geta()&&pos==len){ return 1; } } } for(int i=1;i<10;i++){ pos=0; if(two%i==0&&two/i<10){ a[0]=i; if(getb()&&geta()&&pos==len){ return 1; } } } return 0; } int main(){ ios::sync_with_stdio(0); int t; cin>>t; while(t--){ cin>>n>>m; cin>>s; len=s.size(); if(check()){ for(int i=0;i<n;i++) cout<<a[i]; cout<<" "; for(int i=0;i<m;i++) cout<<b[i]; cout<<"\n"; }else{ cout<<"Impossible\n"; } } return 0; }