nyoj--46--最小乗算回数(数学+テクニック)
774 ワード
最小乗算回数
時間制限:
1000 ms|メモリ制限:
65535 KB
難易度:3
説明
ゼロ以外の整数をあげて、この数のn次方を求めさせて、毎回乗算する結果は後で使うことができて、少なくとも何回乗算する必要がありますかを求めます.例えば24:2*2=22(1回目)、22*22=24(2回目)なので、最低2回です.
入力
第1行mは、m(1<=m<=100)群の試験データを表す.
各試験データのセットには整数n(0しゅつりょく
各テストデータのセットに必要な回数sを出力する.
サンプル入力
サンプル出力
時間制限:
1000 ms|メモリ制限:
65535 KB
難易度:3
説明
ゼロ以外の整数をあげて、この数のn次方を求めさせて、毎回乗算する結果は後で使うことができて、少なくとも何回乗算する必要がありますかを求めます.例えば24:2*2=22(1回目)、22*22=24(2回目)なので、最低2回です.
入力
第1行mは、m(1<=m<=100)群の試験データを表す.
各試験データのセットには整数n(0
各テストデータのセットに必要な回数sを出力する.
サンプル入力
3234
サンプル出力
122
#include<stdio.h>
#include<string.h>
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
int cnt=0;
while(n!=1)
{
if(n&1)
cnt+=2;
else
cnt++;
n/=2;// , +2
}
printf("%d
",cnt);
}
return 0;
}