鏈接： https://www.nowcoder.com/acm/contest/107/G
來源：牛客網

題目描述

眾所周知，汀老師是XDUACM實驗室最優秀的人，無論是學習還是打游戲。今天他突然想到一個好玩的游戲。規則是這樣的，在游戲中他要得到n個小國，初始的時候小國和小杰各有1個。經過了很久的修煉，汀老師學會了兩種魔法，他每次可以動用自己的智慧來使用魔法。

第一個魔法：（小杰變小國）可以將自己的智慧復制和當前小杰一樣數量的小國出來；

第二個魔法：（小國大爆發）可以將當前的小杰變成和小國的數量一樣，然后小國的數量加倍！

因為汀老師的智力是無限多的，他不關心花掉的智力大小。但是好學的汀老師想盡快得到n個小國，使得能有更多的時間去讀paper和打比賽。他想問問你，最少需要使用多少次魔法可以得到n個小國。

得到了n個小國后，汀老師去學習，但是小國們基因突變在電腦里越來越多！他們來組織汀老師學習，現在告訴汀老師我要得到更多的同伴！

輸入描述:

多組數據，第一行一個正整數T(T<=100000)表示數據組數。 接下來T行，每行一個正整數n(n<=10^6)。

輸出描述:

對于每組數據輸出一個整數，表示得到n個小國汀老師最少需要使用多少次膜法。示例1

輸入

2 1 3

輸出

0 2

#include<bits/stdc++.h> using namespace std; typedef long long ll; int vis[1000010]; long long Ans=0; inline void dfs(int x,int now,int sum) {if(x==1) {Ans+=sum*(now-1);return;}if(vis[x]!=now) {Ans+=sum*(now-1);dfs(x/vis[x],vis[x],1);}elsedfs(x/vis[x],now,sum+1); } int main() {memset(vis,0x3f,sizeof vis);vis[1]=1;for(int i=2;i<=1e6;++i)if(vis[i]==0x3f3f3f3f)for(int j=i;j<=1e6;j+=i)vis[j]=min(vis[j],i);int T,x;cin>>T;while(T--) {cin>>x;Ans=0;dfs(x,0,0);cout<<Ans<<endl;} }
與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的西安电子科技大学第16届程序设计竞赛G题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。