题目链接:https://codeforces.com/contest/1062/problem/B
题目大意:给定一个n,你有两种操作,乘以任意数(非零),开根(开根后要是整数),问最找那个能到达的最小值和操作的次数
解题思路:首先易得最小值是n的素因子之积,那么操作次数呢?
通过样例我们发现,每一次操作都可以让素因子的幂除以二,操作次数就是n的素因子的幂先通过乘到达就近的2的幂,然后通过开跟每次除二,又由于乘的数可以是若干个素因子的积,任何数都可以通过一次乘法使得每个素因子的幂是2的x次幂,由此可解。但是特别🐶的是有好多特殊的情况要考虑,比如n是1的时候就不要先乘2再除二了。。。感觉要不是cf可以看后台数据能卡我半天了。。
代码
#include <iostream> #include <bits/stdc++.h> using namespace std; int maxx; int minn; int cnt; int main() { int a; cin>>a; maxx=0; minn=0x3f3f3f3f; int ansa=1,ansb; for(int i=2; i<=1000000; i++) { cnt=0; if(a%i==0) { ansa*=i; } while(a%i==0) { cnt++; a/=i; } if(cnt!=0) { maxx=max(maxx,cnt); minn=min(minn,cnt); } } if(maxx==1||maxx==0) { cout<<ansa<<" 0"<<endl; return 0; } int k=0,pp=1; while(1) { k++; pp*=2; if(pp>=maxx) { break; } } ansb=k; if(minn!=maxx||maxx!=pp) { ansb++; } cout<<ansa<<" "<<ansb<<endl; return 0; }