UVa 1374 Power Calculus （快速幂计算）

分手后的思念是犯贱 2022-09-27 15:29 147阅读 0赞

题意：给出x和正整数n，问最少需要几次乘除法 可以得到n = x^m

//打表法对1~1000的数打表

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    const int ans[]={0,1,2,2,3,3,4,3,4,4,5,4,5,5,5,4,5,5,6,5,6,6,6,5,6,6,6,6,7,6,6,5,6,6,
    7,6,7,7,7,6,7,7,7,7,7,7,7,6,7,7,7,7,8,7,8,7,8,8,8,7,8,7,7,6,7,7,8,7,8,8,8,7,8,8,8,8,
    8,8,8,7,8,8,8,8,8,8,9,8,9,8,9,8,8,8,8,7,8,8,8,8,9,8,9,8,9,9,9,8,9,9,9,8,9,9,9,9,9,9,9,8,
    9,9,9,8,9,8,8,7,8,8,9,8,9,9,9,8,9,9,9,9,9,9,9,8,9,9,9,9,9,9,10,9,9,9,9,9,9,9,9,
    8,9,9,9,9,9,9,10,9,10,9,10,9,10,10,10,9,10,10,10,9,10,10,10,9,10,9,10,9,9,9,9,8,
    9,9,9,9,10,9,10,9,10,10,10,9,10,10,10,9,10,10,10,10,10,10,10,9,10,10,10,10,10,10,
    10,9,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,9,10,10,10,10,10,10,10,9,10,10,
    10,9,10,9,9,8,9,9,10,9,10,10,10,9,10,10,11,10,11,10,10,9,10,10,11,10,11,10,10,10,
    10,10,10,10,10,10,10,9,10,10,10,10,10,10,11,10,10,10,11,10,11,11,11,10,11,10,11,10,
    11,10,11,10,11,10,10,10,10,10,10,9,10,10,10,10,10,10,11,10,11,10,11,10,11,11,11,10,11,11,11,
    10,11,11,11,10,11,11,11,11,11,11,11,10,11,11,11,11,11,11,11,10,11,11,11,11,11,11,11,
    10,11,11,11,10,11,11,11,10,11,10,11,10,10,10,10,9,10,10,10,10,11,10,11,10,11,11,11,10,11,
    11,11,10,11,11,11,11,11,11,11,10,11,11,11,11,11,11,11,10,11,11,11,11,11,11,11,11,
    11,11,11,11,11,11,11,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,10,11,11,11,11,11,
    11,11,11,11,11,11,11,12,11,12,11,11,11,12,11,12,11,11,11,11,11,11,11,11,11,11,10,11,11,
    11,11,11,11,11,11,11,11,12,11,12,11,11,10,11,11,12,11,12,11,11,10,11,11,11,10,11,10,10,9,10,
    10,11,10,11,11,11,10,11,11,12,11,12,11,11,10,11,11,12,11,12,12,11,11,12,12,12,11,12,11,11,10,
    11,11,12,11,12,12,12,11,11,12,12,11,12,11,12,11,11,11,12,11,12,11,11,11,12,11,11,11,11,11,11,10,11,
    11,11,11,11,11,12,11,11,11,12,11,12,12,12,11,12,11,12,11,12,12,12,11,12,12,12,12,12,
    12,12,11,12,12,12,11,12,12,12,11,12,12,12,11,12,12,12,11,12,12,12,11,12,11,12,11,
    12,11,11,11,11,11,11,10,11,11,11,11,11,11,12,11,12,11,12,11,12,12,
    12,11,12,12,12,11,12,12,12,11,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,11,12,12,
    12,12,12,12,12,11,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,11,12,12,12,12,12,12,
    12,12,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,12,12,12,12,12,12,12,
    12,11,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,11,12,12,12,11,12,12,12,11,12,
    11,12,11,11,11,11,10,11,11,11,11,12,11,12,11,12,12,12,11,12,12,12,11,12,12,12,12,
    12,12,12,11,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,12,12,12,13,12,12,12,
    12,11,12,12,12,12,13,12,12,12,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,12,12,
    12,12,12,12,12,13,12,12,12,13,12,13,12,12,12,13,12,12,12,12,12,12,11,12,12,12,12,12,
    12,13,12,12,12,13,12,13,12,12,12,13,12,13,12,13,12,12,12,12,12,12,12,12,12,
    12,11,12,12,12,12,12,12,12,12,12,12,13,12,13,12,13,12,13,12,13,12,13,12,13,12,13,
    13,13,12,13,13,13,12,13,12,13,12,13,13,13,12,13,13,13,12,13,12,13,12,12,12,13,12,
    13,12,12,12,12,12,12,12,12,12,12,11,12,12,12,12,12,12,12,12,12,12,13,12,13,12,
    12,12,12,12,13,12,13,13,13,12,13,13,13,12,13,12,12,11,12,12,13,12,13,13,13,12};
    
    int main()
    {
        int n;
        while(cin>>n&& n)
            cout<<ans[n-1]<<endl;
        return 0;
    }