A30953. 乘法小宇宙一个 n 位数的正整数 A=anan-1…a1 和另一个 2 位数的正整数 B=b2b1 相乘，其乘法展开式如下图所示：其中 C=cn+1cn…c1 是 A 与 b1 相乘的结果，D=dn+1dn…d1 是 A 与 b2 相乘的结果，P=pn+2pn+1…p1 是 A 与 B 相乘的结果。若上图中的每一位数字都在一个给定的非零个位数字集合 S 里，则称 A 和 B 属于同一个乘法小宇宙…
填空题
中等
知识点
题目描述
乘法小宇宙
一个 n 位数的正整数 A=anan-1…a1 和另一个 2 位数的正整数 B=b2b1 相乘，其乘法展开式如下图所示：
其中 C=cn+1cn…c1 是 A 与 b1 相乘的结果，D=dn+1dn…d1 是 A 与 b2 相乘的结果，P=pn+2pn+1…p1 是 A 与 B 相乘的结果。
若上图中的每一位数字都在一个给定的非零个位数字集合 S 里，则称 A 和 B 属于同一个乘法小宇宙 S。
本题给定乘法小宇宙 S 和 A 的位数，请你找出同属于这个乘法小宇宙中的所有 A 和 B。
时间限制：6000 内存限制：65536
输入
输入在一行中给出两个正整数 n（< 8）和 K（≤ 5），分别是 A 的位数和乘法小宇宙 S 中元素的个数。第二行给出 K 个 (0, 10) 区间内的整数，为 S 中的元素。题目保证没有重复元素。数字间以空格分隔。
输出
按照 A 的非递减序输出所有同属于这个乘法小宇宙中的 A 和 B，每行输出一对，数字间以 1 个空格分隔，行首尾不得有多余空格。对同一个 A，按 B 的递增序输出。若没有解，则输出 `No Solution`。
样例输入
样例#1：
4 5
4 2 1 6 5
样例#2：
3 4
9 2 5 6
样例输出
样例#1：
5556 44
6111 24
6111 42
样例#2：
No Solution
参考答案
#include<iostream>
#include<math.h>
using namespace std;
bool flag(int x);
//枚举一个n位数和一个两位数相乘，看每一个数字是否都在集合S里面
int n,k,s[10];
int main(){
cin>>n>>k;
for(int i=0;i<k;i++)
cin>>s[i];
bool f=false; //标记是否找到
for(int i=pow(10,n-1);i<pow(10,n);i++){ //枚举n位数A，从小到大
if(!flag(i)) continue; //A每位不全在集合S
for(int j=10;j<100;j++){ //枚举两位数B
if(!flag(j)) continue; //B每位不全在集合S
int b1=j%10,b2=j/10; //得到B的个位b1和十位b2
//这里有一个坑，图中的C和D两个整数有n+1位，要是乘出来只有n位是不行的
if(i*b1>pow(10,n) && i*b2>pow(10,n))
//判断C、D、P是否都在集合S内
if(flag(i*b1) && flag(i*b2) && flag(i*j)){
f=true;
cout<<i<<' '<<j<<endl;
}
}
}
if(!f) //没找到
cout<<"No Solution"<<endl;
}
//判断 x 里面的每位数是否都在集合S里面
bool flag(int x) {
while(x){
int g=x%10,i; //计算得到x的个位
for(i=0;i<k;i++){ //找g是否在集合s里面
if(s[i]==g) //找到了 提前返回
break;
}
if(i==k) //正常结束，说明没有提前返回，即没找到
return false;
x/=10; //判断完了个位，刷新x，准备判断下一位
}
return true;
}
上一题
下一题