首页 > ACM题库 > HDU-杭电 > HDU 3208-Integer’s Power-组合数学-[解题报告]HOJ
2014
03-06

HDU 3208-Integer’s Power-组合数学-[解题报告]HOJ

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

容斥原理

引入:已知x=y^k,(x,y,k正整数),要使k最大,即y最小。
输入a,b;计算[a,b]中的数的k的和,(2<=a<=b<=10^18),可统计[1,b]和[1,a-1]中数k的和,再相减可得出答案。
因为2^62>10^18;即k<62;可以计算区间上1次方,2次方,3次方..的数的个数;其间会重复计算,j%i==0则会重复计算,需要减去
num[i]-=num[j];(注意:要从后往前减)..最后乘加起来就好了。。
这题坑爹的是计算次方个数时卡精度,因为pow(x,1.0/k)精度丢失了,最明显的是就是[2,1e18]时的9次方的个数为99,就是怎么发现的,
然后就考虑处理精度的问题,其实pow(x,1.0/k)算出的值上下波动不会超过1的。
只要计算{r-1,r,r+1}^k,哪个最靠近x就可以了。计算r+1时会爆64位的,需要在相乘上做判断。

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
 */

 

 

参考:http://www.cnblogs.com/summer-hikaru/archive/2012/11/24/2786078.html


  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,也要很久才能得出结果,本人亲测