题目描述
Codeforces Round 937 (Div. 4)D. Product of Binary Decimals
给你一个数,范围是1~1e5,问能不能用几个二进制数字乘起来得到这个数
例如:121=11×11
14641=11×11×11×11
12221=11×11×101
样例
input
11
121
1
14641
12221
10110
100000
99
112
2024
12421
1001
output
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
YES
解法一:深度优先搜索
#include <iostream>
//#include <bits/stdc++.h>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <set>
#include <map>
#include <vector>
#include <deque>
#include <iomanip>
#include <queue>
#include <utility>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
int shu01[100010];
int h = 1;
int n;
int nt = 0;
void dfs(int ans)
{
if (ans == n) nt = 1;//能乘出来,标记变量被标记
if (nt) return;//已标记,返回
if (ans > n) return;//剪枝
for(int i=1;i<=h-1;i++)
{
if (nt) break;
ans *= shu01[i];
dfs(ans);
ans /= shu01[i];//回溯
if (nt) break;
}
}
int main()
{
int t;
cin >> t;
for (int i = 10; i <= 100000; i++) {//预处理,提前把二进制的数字存进一个数组
string ss = to_string(i);
int fw = 1;
for (int j = 0; j < ss.length(); j++) {
if (ss[j] != '0' && ss[j] != '1') {
fw = 0;
break;
}
}
if (fw) shu01[h++] = i;
}
while (t--)
{
cin >> n;
string s = to_string(n);
int ok = 1;
for (int i = 0; i < s.length(); i++) {//直接特判,看看这个数字原本就是不是二进制数字
if (s[i] != '0' && s[i] != '1') {
ok = 0;
break;
}
}
if (ok) {
cout << "YES" << endl;
continue;
}
dfs(1);//指数型枚举,枚举了一个数组内任意几个数的相乘的所有可能
if (nt) cout << "YES" << endl;
else cout << "NO" << endl;
nt = 0;
}
return 0;
}
解法二:直接列举:
由于给的数据范围比较小,所以可以直接暴力列出在1e5内所有的类似二进制数,并判断他们是否能相乘等于给定的数
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int a[N];
void solve()
{
string s;
cin >> s;//输入的数字用字符串存储
int n = stoi(s);//将字符串转化为十进制数
int falg = 1;
for (int i = 0; i < s.size(); i++) {//判断是否都是1或者0,如果是则直接输出yes
if (s[i] != '0' && s[i] != '1') {
falg = 0;
break;
}
}
if (falg) {
cout << "YES" << endl;
return;
}
//1e5内所有的类似二进制的数为以下几个,依次相除,从小到大,能除的都除了
//联想分解质因子,有他的味道
while (n % 10 == 0) {
n /= 10;
}
while (n % 11 == 0) {
n /= 11;
}
while (n % 101 == 0) {
n /= 101;
}
while (n % 111 == 0) {
n /= 111;
}
while (n % 1001 == 0) {
n /= 1001;
}
while (n % 1011 == 0) {
n /= 1011;
}
while (n % 1101 == 0) {
n /= 1101;
}
while (n % 1111 == 0) {
n /= 1111;
}
//最后判断是否能被整除
if (n == 1) {
cout << "YES" << endl;
return;
}
else {
cout << "NO" << endl;
}
}
signed main()
{
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}