题解 CF1176A 【Divide it!】

## Solution 这是一道数学题啊！！~~给点对他的尊重好吗？~~ 这题刚刚看到的时候，心里的第一个反应就是$dfs$——毕竟这是A题嘛！复杂度也不大，就是$\Theta(3^n.q)$（逃……）。结果看到了这样一个东西：$1\le n \le 10^{18},1\le q \le 1000$。 内心是自闭的，于是开始想正解…… 通过仔细观察题目，发现要求最小的步数，于是我们就尽量通过最少的步数让$n$的值最小，所以若$n | 5$时，就把$n$变成$\dfrac{4}{5}n$，$n|3$时，就把$n$变成$\dfrac{2}{3}n$，当$n|2$时，就把$n$变成$\dfrac{1}{2}n$。 然后照着这个思路敲代码就好啦，复杂度大约是$\Theta(q)$，但是常数巨大，但是还能过。 ## code ```cpp #include <bits/stdc++.h> using namespace std; int q; int main() { scanf("%d",&q); while(q--) { long long cnt = 0,n; scanf("%lld",&n); while(n % 5 == 0) { n = n / 5 * 4; cnt++; } while(n % 3 == 0) { n = n / 3 * 2; cnt++; } while(n % 2 == 0) { n /= 2; cnt++; } if(n == 1) printf("%d\n",cnt); else puts("-1"); cnt = 0; } } ```