c - 非斜边数

non-hypotenuse number是自然数，其平方不能写成两个非零平方之和。

给定两个整数a和b，任务是找到范围[L，R]中所有奇数长度的非斜边数之和，其中𝐿=𝑎和𝑅= 𝑏²−2-2 ^𝑎。

例如，如果a = 2且b = 5，则L = 2且R = 5²−2² = 21。此范围的非斜边数为：2、3、4、6、7、8、9、11 12、14、16、18、19、21。但是由于我们在求和中只包括奇数个长度，因此最终结果是：39 = 2 + 3 + 4 + 6 +7 + 8 +9。

对于输入5 25，它返回65590；但是，应该返回72483。它适用于输入2 5和4100。我在做什么错？

这是我的代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

//function, that returns 1 if it is a nonHypoNum
int isNonHypo(int x){
    double temp;
    for (int i=1; i<x; i++){ //iterates through the possible lengths of one leg of the triangle
        temp=sqrt((double)(x*x-i*i)); //calculate third leg
        if (temp==(int)temp) //if the third is a whole number
            return 0;
    }
    return 1;
}

//function, that tells weather it has an odd number off digits
int isOddLength(int x){
    int digits=0;
    while (x){
        digits++;
        x/=10;
    }
    return (digits%2==0?0:1);
}

//function, that returns the power of two
int powTwo(int exp){
    int x=2;
    for (;exp>0;exp--){
        x*=2;
    }
    return (x);
}

int main(){
    int a,b,sum=0;

    scanf("%d%d",&a,&b);
    for (int Hypo=a; Hypo<=(b*b-powTwo(a)); Hypo++){ //try out numbers in range [a,b²-2^a]
        if (isOddLength(Hypo)&&isNonHypo(Hypo))
            sum+=Hypo;
    }
    printf("%d",sum);
    return 0;
}

最佳答案

您的代码中此行存在一些数字问题

temp = sqrt((double)(x*x-i*i));  // where 'temp', 'x' and 'i' are int

x*x和i*i都可能溢出。结果是否强制转换为double无关紧要，因为它在执行乘积后发生。您应该使用更大的类型，例如long long，并在乘法之前强制转换值。在这种情况下，对double的强制转换甚至可能会引入一些舍入错误。
将sqrt的结果分配给int可能还会引入一些不必要的舍入错误。您可以使用round()防止出现这些情况。


在这种情况下，您可以改用sqrt并使用其他算法保存一些迭代：

#include <stdbool.h>

static inline long long sq(int x)
{
    return (long long)x * x;
}

bool is_nonhypotenuse(int x)
{
    long long square_x = sq(x);

    // Meet in the middle, instead of going up to x
    for (int i = 1, j = x - 1; i <= j; i++)
    {
        long long square_j, target = square_x - sq(i);

        // Iterates, instead of calculating the square root
        while ( (square_j = sq(j)) > target )
            --j;
        if ( square_j == target )
            return false;
    }
    return true;
}

编辑

另一个问题（可能是最重要的，给定输入数据）在于用于计算2的幂的函数。

int powTwo(int exp) {
    int x=2;                    // <-- It should start from 1, here
    for (;exp>0;exp--) {
        x*=2;
    }
    return (x);                 // <-- Effectively returns 2^(exp + 1)
}

您可以考虑使用这种更通用的方法。

long long int_pow(int base, int exp)
{
    long long result = 1;
    while ( exp )
    {
        if (exp & 1)
            result *= base;
        exp /= 2;
        base *= base;
    }
    return result;
}

或者，假设底数为2，则只需使用一位移位

int R = b * b - (1 << a);

进行这些修改后，您的程序应输出所需的值。参见例如here。

关于c - 非斜边数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58166218/