class="markdown_views prism-atom-one-light">

小国的复仇

• 小国的复仇
  • 题意
  • 思路一
  • 思路二
  • 代码一
  • 代码二

题目链接：西安电子科技大学第16届程序设计竞赛网络同步赛 - 小国的复仇

---

题意

​ 给你两个数a = 1,b = 1。你有两个操作可以选择，（1）a = a+b （2）b = a , a = a*2 。然后给你一个n，求如何经过最小的操作数，来达到 a = n；题目限制：n(n<=10^6)，T(T<=100000)

---

思路一

​ 如果这个给的n和T不是那么大的话，就选择宽搜了，但是这种数据量明显只允许出现 O(logn) 或 O(1) 的算法。我就开始了找规律，如果因为操作二会改变b的值，在操作二以后，操作一也只能加上修改过的b的值了，所以我们不难得出，要执行操作二，必须要保证n是a的倍数，否则不能执行操作二，而且操作二的增长幅度很快，是指数级别的，我就想能不能先执行操作二，直到操作二无法进行时在执行操作一。但是这样的代码只过了50%的样例，所以显然有什么不对的地方。

---

思路二

​ 果然，在我测试到9的时候，就发现了不对，原本的代码输出时8，但是如果先进行了两次操作一，再进行操作二，最后的结果就只需要4次了。我又开始考虑起了原来发现的规律，那就是一个n的操作数，一定是由一个n的因子的操作数经过变化得到，那么只需要得到它所有的因子，再进行例如DP一样的递推即可，但是这个操作会很复杂，我要先得到一个数的所有因子，这个就基本告吹了，在T= 1e5的情况下，百分百会炸。但在换一个角度来看又会不一样了，例如素数筛，基本可以访问每个因子的倍数，而且经过预处理后，只有1e6的数据量也不会炸的。

---

代码一

#include using namespace std; #define rep(i,j,k) for(int i = (int)(j);i <= (int)(k);i ++) #define per(i,j,k) for(int i = (int)(j);i >= (int)(k);i --) typedef long long ll; const int MAXN = (int) 1e6+7; const int INF = (int) 0x3f3f3f3f; int dp[MAXN]; int bi[MAXN]; int an(int N,int i,int &e){ int ans = 0; int a = i,b = bi[i]; while (N % a == 0 && N >= 2*a){ b = a; a *= 2; ans ++; } ans += (N-a)/b; e = b; return ans+dp[i]; } int main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); memset(dp,0x3f,sizeof(dp)); dp[1] = 0; dp[2] = 1; bi[1] = 1; int e; for (int i = 1;i < MAXN;i ++){ for (int j = 2;j*i < MAXN;j ++){ if (i != 1)Prime[j*i] = 1; int aaaa = an(i*j,i,e); if (dp[i*j] > aaaa){ bi[i*j] = e; dp[i*j] = aaaa; } } } int T; cin >> T; while (T --){ int n; cin >> n; cout << dp[n] << endl; } }

代码二

//大神代码，思路非常清楚，筛法用起来比我要方便很多 #include using namespace std; int T,n,a[1000005]; int main(){ memset(a,0x3f,sizeof(a)); a[1]=0; for(int i=1; i<=1000000; ++i) for(int j=i; j+i<=1000000; j+=i) a[j+i]=min(a[j+i],a[i]+j/i); scanf("%d",&T); while(T--){ scanf("%d",&n); printf("%d ",a[n]); } }