[C++知识库]Math master (爆搜二进制枚举)

Math master

[Link](Problem - D - Codeforces)

题意

给你$p,q$分别是分子和分母，请你从分子和分母中删除一些数，保证分子和分母删除的数一样且删除完以后的数$x/y$和原来的数最简形式一样，求这样操作后分子最小的数是什么。

题解

数据范围是$2^{63}$，因此不超过$19$位。我们可以二进制暴力枚举分子$x$每一位选不选，再通过最简形式一样搞出来分母$y$，如果$x$,$y$符合删除的数一样，就判断一下是否可以更新答案即可。

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <bitset>
#include <unordered_map>
#include <cmath> 
#include <stack>
#include <iomanip>
#include <deque> 
#include <sstream>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
#define tpyeinput int
inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
inline void read(tpyeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k, cnt[110];
vector<LL> numa, numb;
LL p, q;
vector<LL> get(LL x) {
    vector<LL> res;
    while (x) {
        res.push_back(x % 10);
        x /= 10;
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
    cin >> T;
    while (T -- ) {
        cin >> p >> q;
        LL resa = p, resb = q;
        numa = get(p), numb = get(q);
        int sza = numa.size(), szb = numb.size();
        LL d = __gcd(p, q); p /= d, q /= d;
        for (int op = 1; op < (1 << sza); op ++ ) {
            for (int i = 0; i < 10; i ++ ) cnt[i] = 0;
            LL fz = 0;
            for (int i = sza - 1; i >= 0; i -- ) 
                if (op >> i & 1)     fz = fz * 10 + numa[i];
                else cnt[numa[i]] ++;
            if (!fz || fz % p) continue ;
            LL fm = fz / p * q, tmp = fm;
            for (int i = 0; i < szb; i ++ ) {
                if (tmp % 10 != numb[i]) cnt[numb[i]] --;
                else tmp /= 10; 
            }
            if (tmp) continue ;
            bool ok = false;
            for (int i = 0; i < 10; i ++ )  if (cnt[i]) ok = true;
            if (ok) continue ;
            if (fz < resa) resa = fz, resb = fm;
        }
        cout << resa << ' ' << resb << endl;
    }
    return 0;
}