这个 an + bnlog2(n) + cn3 = k，在这里为更大的输入找到 n 不能正常工作

Question

我必须在考试中解决问题。但它无法通过所有测试用例。就是这个等式。

an + bnlog2(n) + cn3 = k 其中给定了 a,b,c,k。该位置最大为 2^63 -1

假设输入是

input:

2 1 1 12167000368000

2 1 1 188000000000000

output:

23000

0

这是我的解决方案

#include<stdio.h>

long long Log2n(long long n)
{
     return (n > 1)? 1 + Log2n(n/2): 0;
 }

int main(){
  long long a,b,c,k, pos, flag = 0;
   scanf("%lld%lld%lld%lld",&a,&b,&c,&k);
   for(int i=0; i<100000000; i++){
        pos = a*i + b*i*Log2n(i)+ c*(i*i*i);
          if(pos == k){
             printf("%lld ",i);
               flag = 1;
                break;
              }
         }
    if(flag == 0){
      printf("0");
    }
  return 0;
 }

像小输入 2 1 1 36 它给出了正确的输入。但是当 k 的输入很大或者数字不是这个时，它就不能正常工作。

我认为我的迭代有问题。这个迭代应该进行多少次？还是有更好的解决方案来找到这个 n 值？

Answer 1

由于 i 声明为 int，(i*i*i) 将溢出并调用未定义的行为。

您应该在 pos 的计算中将 i 声明为 long long 或将 i 转换为 long long。

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

应该是

 for(long long i=0; i<100000000; i++)

限制 100000000 似乎有点武断，应该进行调整，因为即使 long long 也可能会溢出。

对long long的更改当然不是通用的解决方案，但适用于测试用例。应该大量使用的类型取决于输入变量的域。

Answer 2

请注意 a*i + b*i*Log2n(i)+ c*i*i*i 与 (a + b*Log2n(i)+ c*i*i) * i 基本相同。

这意味着（为了减少溢出的风险）你可以这样做：

    if(k % i == 0) {
        pos_divi = a + b*Log2n(i)+ c*i*i;
        if(pos_divi == k / i) {
             printf("%lld ",i);
             flag = 1;
             break;
        }
    }

Answer 3

我想 k > 0

我们搜索 n^3(a/n^2 + b log2(n)/n^2 + c)= k

需要根据c> 0、c = 0、c <0

处理几种情况

我离开案例 c = 0，我们将通过 nlog2(n)

进行因式分解

假设c>0。作为 lim |a/n^2| = 0 (n-> +oo) 和 lim |b log2(n)/n^2| = 0 (n-> +oo) 存在 p，例如 n>p、|a/n^2| < c/4 和 |b log2(n)/n^2| < c/4

我们可以通过编程方式搜索这样的整数 p

所以 -c/4 < a/n^2 < c/4 和 -c/4 < blog2(n)/n^2 < c/4

因此 n>p、n^3*c/2 <= k <= n^3*3*c/2 然后 2k/(3c) <= n^3 <= 2k / c

这简化了对 n ...

的搜索

如果 c < 0 我们可以通过递增 n 并将左侧成员与 k 进行比较并在该成员变为负数时停止来进行循环。

这个 an + bnlog2(n) + cn3 = k，在这里为更大的输入找到 n 不能正常工作

This an + bnlog2(n) + cn3 = k, finding n here for bigger input is not working properly

c

algorithm

optimization

equation