hdu 3208 Integer’s Power 筛法

时间：2023-03-09 16:32:03
hdu 3208 Integer’s Power 筛法

Integer’s Power

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Problem Description
LMY and YY are number theory lovers. They like to find and solve some interesting number theory problems together. One day, they become interested in some special numbers, which can be expressed as powers of smaller numbers.

For example, 9=3^2, 64=2^6, 1000=10^3 …

For a given positive integer y, if we can find a largest integer k and a smallest positive integer x, such that x^k=y, then the power of y is regarded as k.
It is very easy to find the power of an integer. For example:

The power of 9 is 2.
The power of 64 is 6.
The power of 1000 is 3.
The power of 99 is 1.
The power of 1 does not exist.

But YY wants to calculate the sum of the power of the integers from a to b. It seems not easy. Can you help him?

Input
The input consists of multiple test cases.
For each test case, there is one line containing two integers a and b. (2<=a<=b<=10^18)

End of input is indicated by a line containing two zeros.

Output
For each test case, output the sum of the power of the integers from a to b.
Sample Input
2 10
248832 248832
0 0
Sample Output
13
5
Source

思路：卡精度；

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<bitset>

#include<set>

#include<map>

#include<time.h>

using namespace std;

#define LL long long

#define pi (4*atan(1.0))

#define eps 1e-8

#define bug(x)  cout<<"bug"<<x<<endl;

const int N=1e4+,M=1e6+,inf=1e9+;

const LL INF=1e18+,mod=1e9+;

LL big[]={,,,,};

const LL T=(LL)<<;

LL multi(LL a,LL b)

{

    LL ans=;

    while(b)

    {

        if(b&)

        {

            double judge=1.0*INF/ans;

            if(a>judge) return -;

            ans*=a;

        }

        b>>=;

        if(a>T&&b>) return -;

        a=a*a;

    }

    return ans;

}

LL findd(LL x,LL k)

{

    LL r=(LL)pow(x,1.0/k);

    LL t,p;

    p=multi(r,k);

    if(p==x) return r;

    if(p>x||p==-) r--;

    else

    {

        t=multi(r+,k);

        if(t!=-&&t<=x) r++;

    }

    return r;

}

LL dp[];

LL xjhz(LL x)

{

    memset(dp,,sizeof(dp));

    dp[]=x-;

    for(int i=;i<=;i++)

    {

        int s=,e=big[i],ans=-;

        while(s<=e)

        {

            int mid=(s+e)>>;

            if(multi(mid,i)<=x)

            {

                ans=mid;

                s=mid+;

            }

            else e=mid-;

        }

        if(ans!=-)dp[i]=ans-;

    }

    for(int i=;i<=;i++)

    {

        dp[i]=findd(x,i)-;

    }

    for(int i=;i>=;i--)

    {

        for(int j=i+i;j<=;j+=i)

            dp[i]-=dp[j];

    }

    LL out=;

    for(int i=;i<=;i++)

        out+=1LL*i*dp[i];

    return out;

}

int main()

{

    LL l,r;

    while(~scanf("%lld%lld",&l,&r))

    {

        if(l==&&r==)break;

        printf("%lld\n",xjhz(r)-xjhz(l-));

    }

    return ;

}

Integer’s Power

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

Problem Description
LMY and YY are number theory lovers. They like to find and solve some interesting number theory problems together. One day, they become interested in some special numbers, which can be expressed as powers of smaller numbers.

For example, 9=3^2, 64=2^6, 1000=10^3 …

For a given positive integer y, if we can find a largest integer k and a smallest positive integer x, such that x^k=y, then the power of y is regarded as k.
It is very easy to find the power of an integer. For example:

The power of 9 is 2.
The power of 64 is 6.
The power of 1000 is 3.
The power of 99 is 1.
The power of 1 does not exist.

But YY wants to calculate the sum of the power of the integers from a to b. It seems not easy. Can you help him?

Input
The input consists of multiple test cases.
For each test case, there is one line containing two integers a and b. (2<=a<=b<=10^18)

End of input is indicated by a line containing two zeros.

Output
For each test case, output the sum of the power of the integers from a to b.
Sample Input
2 10
248832 248832
0 0
Sample Output
13
5
Source

相关文章