为什么spoj为这个“Integer功能”的解决方案提供了错误的答案？

Question

我正试图解决关于spoj的INTEGER1问题。我的方法非常简单。它首先计算从2到63的所有幂的x（x^i = n）。然后删除所有重复，然后最终累加幂。但它正在给我错误的答案。 我已经在Ideone和我的机器上尝试了很多用例，但它给了我正确的结果。

#include<stdio.h> 
#include<math.h> 
int main() 
{ 
    unsigned long long int a,b,result; 
    unsigned long long int power[65],temp; 
    int i,j; 

    while(1) 
    { 
     scanf("%lld",&a); 
     scanf("%lld",&b); 
     if(a==0) 
      break; 
     result=0; 
     power[0]=0; 
     power[1]=b-a+1; 

     a--; 
     for(i=2;i<64;i++) 
     { 
      power[i]=floor(pow((long double)b,(long double)1/i)); 
      while(pow((power[i]-1),(long double)i)>=b) 
      { 
       power[i]--; 
      } 
      while(pow((power[i]+1),(long double)i)<=b) 
      { 
       power[i]++; 
      } 

      temp=floor(pow((long double)a,(long double)1/i)); 
      while(pow((temp-1),(long double)i)>=a) 
      { 
       temp--; 
      } 
      while(pow((temp+1),(long double)i)<=a) 
      { 
       temp++; 
      } 
      power[i]-=temp; 
     } 
     for(i=63;i>=1;i--) 
     { 
      for(j=i*2;j<64;j=j+i) 
      { 
       power[i]-=power[j]; 
      } 
     } 
     for(i=1;i<64;i++) 
     { 
      result+=i*power[i]; 
     } 
     printf("%lld\n",result); 
    } 

    return 0; 
} 

请帮我一把。

Answer 1

为输入

100 100 
10000 100000000 
100000000000 100000000000 
100000000000000 100000000000000 
1000000000000000 1000000000000000 
0 0 

你的输出

2 
100001508 
11 
14 
11 

但正确的输出是

2 
100001508 
11 
14 
15 

现在寻找的akth根..doing一些数学

let x = a^(1/k) (^ denotes power NOT XOR)(this is also `kth` root of `a`) 

采取自然对数（LN）双方

ln x = ln (a^(1/k)) = (1/k) * ln (a) {property of log} 

现在正在exponent双方

exp (ln x) = exp (ln (a)/k) 

，并根据log财产

exp (ln x) = x 

所以我们最终得到

x = exp (ln(a)/k) which is equivalent to `kth` root of `a` 

这里是一个功能找到它在C

记得在数学上，我们使用ln寻找自然对数这C

等同于的 log

double kth_root_finder(long long int a, long long int k) { 
    if (k == 1) { 
     return a; 
    } 
    if (k == 2) { 
     return sqrt(a); 
    } 
    return exp(log(a)/k); 
} 

编辑1：-as在OP指出，会出现溢出，但我不这么认为它会happen..consider我们有

a = 1000000000000000000 and k = 2 (worst case)(ignoring second if condition) 

然后

exp(log(1000000000000000000)/2) = 999999999.999999 = 1000000000(if ceil is taken) 

here是一个链接，上面的情况.. 所以我不认为有机会overflow ..如果其中有请指出..