快速幂&&二分&&A Math Problem

柔光的暖阳◎ 2022-05-27 12:28 162阅读 0赞

题目链接：[点击打开链接][Link 1]

# A Math Problem #

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

Problem Description

You are given a positive integer n, please count how many positive integers k satisfy  k![Image 1][]k![Image 1][]≤n![Image 1][].

Input

There are no more than 50 test cases.  
  
Each case only contains a positivse integer n in a line.  
  
 1≤n≤10![Image 1][]18![Image 1][]![Image 1][]

Output

For each test case, output an integer indicates the number of positive integers k satisfy  k![Image 1][]k![Image 1][]≤n![Image 1][] in a line.

Sample Input

1
    4

Sample Output

1
    2

//切记此题不能调用pow()函数
    //二分实现
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll n;
    int check(int x)
    {
       ll a=1;
       for(int i=1;i<=x;i++)
       {
           a=a*x;
       }
        if(a<=n) return 1;
        else return 0;
    }
    int main()
    {
        while(cin>>n)
        {
            int l=1,r=15;
            int ans=1;
            while(l<=r)
            {
                int mid=(l+r)/2;
                if(check(mid))
                {
                    ans=mid;
                    l=mid+1;
                }
                else
                {
                    r=mid-1;
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }
    //快速幂实现
    #include<stdio.h>
    #include<string.h>
    typedef long long ll;
    ll n;
    ll quick(int x)
    {
        ll a=1;
        ll b=x;
        ll sum=x;
        while(b)
        {
            if(b&1)
            {
                a=a*sum;
            }
            sum=sum*sum;
            b>>=1;
        }
        return a;
    }
    int main()
    {
        while(scanf("%lld",&n)!=EOF)
        {
            for(int i=15;i>=1;i--)
            {
                ll a=quick(i);
                if(n>=a)
                {
                    printf("%d\n",i);
                    break;
                }
            }
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6182
[Image 1]: