首页 > 技术文章 > [xdoj1029]求解某个数的最高位和最低位

elpsycongroo 2017-06-01 01:54 原文

解题关键:

1、最高位求法

long long int x=n^m; 
式子两边同时取lg lg(x)=m*lg(n); 
x=10^(m*lg(n)); 
10的整数次方的最高位一定是1,所以x的最高位取决于m*lg(n)的小数部分 
k=m*lg(n)的小数部分=m*lg(n)-floor(m*lg(n)); 
x的最高位=floor(10^k);

注意浮点数会有误差,所以,通不过时要加点小数

2、最低位求法

普遍情况下可以运用快速幂求解,而本题由于是2的n次幂,所以可以直接用打表求解。

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int b[100]={2,4,8,6};
int main(){
    int t,n,t2;
    double m,x;
    cin>>t;
    while(t--){
        cin>>n;
        t2=(n-1)%4;
        x=n*log10(2.0);
        x-=(int)x;
        m=(int)(pow(10.0,x)+0.000001);
        cout<<m<<" "<<b[t2]<<endl;
    }
}

 

推荐阅读