2017ACM/ICPC广西邀请赛-重现赛 1001 A Math Problem

2017-08-31 16:48:00

writer：pprp

这个题比较容易，我用的是快速幂

写了一次就过了

题目如下：

A Math Problem

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0

Problem Description

You are given a positive integer n, please count how many positive integers k satisfy k ^ k <= n

Input

There are no more than 50 test cases.

Each case only contains a positivse integer n in a line.

1≤n≤10^18 

Output

For each test case, output an integer indicates the number of positive integers k satisfy k^k≤n in a line. 

Sample Input

1 4 

Sample Output

1 2

Input

There are no more than 50 test cases.

Each case only contains a positivse integer n in a line.

1≤n≤10^18

 

题目分析：

给你一个n，问你最大的 k ^ k <= n的 k的值，你可以用电脑上自带的计算器算一算，大概范围15^15就已经超过18位了，所以可以从15开始倒着枚举

 

代码如下：

#include <iostream>

using namespace std;
typedef long long ll;

//a ^ a
__int64 POW(ll a)
{
    __int64 result = 1;
    ll base = a;
    ll tmp = a;
    while(tmp > 0)
    {
        if((tmp & 1) == 1)
            result = result * base;
        base = base * base;
        tmp >>= 1;
    }
    return result;
}

//int main()
//{
//    ll a;
//    cin >> a;
//    cout << POW(a) << endl;
//
//    return 0;
//}

int main()
{
    ios::sync_with_stdio(false);
    __int64 n;
    while(cin >> n)
    {
        for(int i = 15 ; i >= 0 ; i--)
        {
            if(POW(i) <= n)
            {
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
}