2014
03-06

# Integer’s Power

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?

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.

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.

2 10
248832 248832
0 0

13
5

num[i]-=num[j];(注意：要从后往前减)..最后乘加起来就好了。。

AC代码：

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#define ll __int64
#define inf (ll) 1e18+300
#define eps 1e-9
using namespace std;
ll why=(ll)1<<31;
ll num[100];
ll quickpow(ll m,int n)
{
ll b=1;int k=n;
while (n>0)
{
if (n&1)
{
double judge=1.0*(inf)/b;
if (judge<m) return -1;//避免b*m爆64
b*=m;
}
n=n>>1;
if (m>why&&n>0) return -1;//避免m*m爆64
m=m*m;
}
return b;
}
ll find(ll x,int k)
{
ll l=1,r=(ll)pow(x,1.0/k);
ll tt,pp,qq;
pp=quickpow(r,k);
if (pp==x) return r;
if (pp>x||pp==-1) --r;
else
{
tt=quickpow(r+1,k);
if (tt!=-1&&tt<=x) ++r;
}
return r;
}
ll f(ll x)
{
int i,j,k;
ll ans=0;
if (x<=3) return x;
memset(num,0,sizeof(num));
num[1]=x;
for (i=2;i<63;++i)
{
num[i]=find(x,i)-1;
if (!num[i]) break;
}
k=i;
for (i=k-1;i>0;--i)
{
for (j=1;j<i;++j)
if (i%j==0) num[j]-=num[i];
}
ans=num[1];
for (i=2;i<k;++i)
{
ans+=(i*num[i]);
}
return ans;
}
int main ()
{
ll a,b;
while (scanf("%I64d%I64d",&a,&b)&&(a+b))
{
printf("%I64d\n",f(b)-f(a-1));
}
return 0;
}
/*
2 1000000000000000000
123 4564651321324813
12 132465786543132132

1000000001002087980
4564651389245135
132465786908165783
*/

1. 第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。

2. 老实说，这种方法就是穷举，复杂度是2^n，之所以能够AC是应为题目的测试数据有问题，要么数据量很小，要么能够得到k == t，否则即使n = 30，也要很久才能得出结果，本人亲测

3. 老实说，这种方法就是穷举，复杂度是2^n，之所以能够AC是应为题目的测试数据有问题，要么数据量很小，要么能够得到k == t，否则即使n = 30，也要很久才能得出结果，本人亲测