Негипотенузное число

Question

A число не-гипотенузы - это натуральное число, квадрат которого нельзя записать в виде суммы двух ненулевых квадратов.

Учитывая два целых числа a и b, задача состоит в том, чтобынайти сумму всех чисел негипотенузы нечетной длины в диапазоне [L, R], где ? = ? и ? = ?² − 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 и 4 100. Что я делаю не так?

Вот мой код:

#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;
}

Answer 1

Есть некоторые числовые проблемы с этой строкой в ​​вашем коде

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);

С этими изменениями ваша программа должна вывестижелаемое значение. См. Например здесь .