Integer’s Power

acm

• 题意：Integer’s Power
  给定区间 [l,r] ,求改区间中能够表示为x^k( x尽量小, k尽量大 )的数的个数
• 问题转化：
  转化为求区间 [1，l-1] 和 [1,r] 的个数，两数相减便是答案
• 分析：
  题目中 (2 <= a <= b <= 10^18 < 2^62 )
  因此我们可以从指数2开始枚举到62
  对于k=1的情况我们单独考虑
  i为指数大小，num[i]为指数对应的个数减1
  num[1] = n，表示所有数均有指数为1的情况（把1的power值也看为1）
  通过使用pow( n, 1.0/k )
  可以求出指数为k的数的个数
  但是这并不一定是满足要求的数，比如64=2^6=8^2 就会出现重复计数。
  我们再通过容斥原理来去除重复。
  最后累加i*num[i]得到答案
• 注意：
  
  1. 使用r = pow( x, 1.0/k )会产生精度误差
     这时我们再计算(r-1)^k r^k (r+1)^k,寻找最接近x的值所对应的r
  2. 同时在计算(r+1)^k的时候还可能会造成溢出
     所以在fast_pow函数中要进行相应处理

    代码君

#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const LL INF = 1e18 + 233;
const LL T = ( LL ) 1 << 31;
LL num[62], l, r;
LL fast_pow( LL a, LL b )
{
    LL ans = 1;
    while( b )
    {
        if( b & 1 )
        {
            double t = 1.0 * (INF)/ans;
            if( a > t ) return -1;
            ans = ans * a;
        }
        b >>= 1;
        if( a > T && b > 0 ) return -1;
        a = a * a;
    }
    return ans;
}
LL find( LL x, LL y )
{
    LL r = ( LL )pow( x, 1.0/y );
    LL t, p;
    p = fast_pow( r, y );
    if( p == x ) return r;
    if( p > x || p == -1 ) r--;
    else
    {
        t = fast_pow( r+1, y );
        if( t != -1 && t <= x ) r++;
    }
    return r;
}
LL solve( LL n )
{
    int s;
    for( int i = 0; i < 62; ++i )
        num[i] = 0;
    if( n <= 3 ) return n;
    num[1] = n;
    for( s = 2; s < 63; ++s )
    {
        num[s] = find( n, s ) - 1;
        if( !num[s] ) break;
    }
    for( int i = s - 1; i > 0; --i )
        for( int j = 1; j < i; ++j )
            if( i % j == 0 )
                num[j] -= num[i];
    LL ans = num[1];
    for( int i = 2; i < s; ++i )
        ans += ( i * num[i] );
    return ans;
}
int main()
{
    while( ~scanf( "%I64d %I64d", &l, &r ) && ( l + r ) )
    {
        printf( "%I64d\n", solve(r) - solve( l - 1 ) );
    }
    return 0;
}