首页 > 其他 > 详细

题解 CF1374B 【Multiply by 2, divide by 6】

时间:2020-10-18 12:31:32      阅读:0      评论:0      收藏:0      [点我收藏+]

维持咕值,被迫营业。

题意

给你一个整数 \(n\)

每次操作可以把 \(n \to n * 2\) 或者 \(n \to n / 6\)

第二种必须满足 \(n\)\(6\) 的倍数。

题解

考虑 \(n\) 的因子。

因为操作二只可以抵消因子 \(2\)\(3\)

如果有除了 \(2\)\(3\) 的其他因子,那么直接 \(puts("-1");\)

然后如果 \(2\) 的因子个数大于 \(3\) 也直接 \(puts("-1");\)

最后就是合法的了,因为 \(2\) 需要去补 \(3\) 多出来的,所有两者的差值需要乘二。

假设 \(num\)\(2\) 的因子个数,\(sum\)\(3\) 的因子个数,那么就只要 \(printf("%d\n", num + (sum - num) * 2);\)

代码

// #include <iostream>
// #include <cstdio>
// #include <algorithm>
// #include <cstring>
// #include <vector>
#include <bits/stdc++.h>
#define maxn 100001
#define ls x << 1
#define rs x << 1 | 1
#define inf 0x3f3f3f3f
#define inc(i) (++ (i))
#define dec(i) (-- (i))
#define mid ((l + r) >> 1)
// #define int long long
#define XRZ 1000000003
#define debug() puts("XRZ TXDY");
#define mem(i, x) memset(i, x, sizeof(i));
#define Next(i, u) for(register int i = head[u]; i ; i = e[i].nxt)
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout);
#define Rep(i, a, b) for(register int i = (a) , i##Limit = (b) ; i <= i##Limit ; inc(i))
#define Dep(i, a, b) for(register int i = (a) , i##Limit = (b) ; i >= i##Limit ; dec(i))
int dx[10] = {1, -1, 0, 0};
int dy[10] = {0, 0, 1, -1};
using namespace std;
inline int read() {
    register int x = 0, f = 1; register char c = getchar();
    while(c < ‘0‘ || c > ‘9‘) {if(c == ‘-‘) f = -1; c = getchar();}
    while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - 48, c = getchar();
    return x * f;
} long long Ans; int a[maxn];//, head[maxn];
priority_queue<int> Q[maxn]; vector<int> s, qwq[maxn];
// struct node { int nxt, to;} e[maxn << 1];
// void add(int x, int y) { e[inc(cnt)] = (node) {head[x], y}; head[x] = cnt;}
void merge(int x, int y) {
      if(Q[x].size() < Q[y].size()) swap(Q[x], Q[y]);
      while(Q[y].size()) {
            s.push_back(max(Q[x].top(), Q[y].top()));
            Q[x].pop(), Q[y].pop();
      }
      while(s.size()) Q[x].push(s.back()), s.pop_back();
}
void Dfs(int x) {
      // Next(i, x) { int v = e[i].to; Dfs(v); merge(x, v);}
      Rep(i, 0, qwq[x].size() - 1) Dfs(qwq[x][i]), merge(x, qwq[x][i]);
      Q[x].push(a[x]);
}
signed main() { int t = read();
	while(t --) { int n = read(), num = 0, sum = 0;
            while(n % 2 == 0) n /= 2, num ++;
            while(n % 3 == 0) n /= 3, sum ++;
            if(n != 1) puts("-1");
            else if(num > sum) puts("-1");
            else printf("%d\n", num + (sum - num) * 2);
      }
      return 0;
}

题解 CF1374B 【Multiply by 2, divide by 6】

原文:https://www.cnblogs.com/Flash-plus/p/13834207.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号