Модульные кубики в C #

Question

Мне трудно решить эту проблему:

Для положительного числа n определите C (n) как число целых чисел x, для которых 1

Когда n = 91, существует 8 возможных значений для x, а именно: 9, 16, 22, 29, 53, 74, 79, 81. Таким образом, C (91) = 8.

Найдите сумму положительных чисел n <= 10 ^ 11, для которых C (n) = 242. </p>

Мой код:

double intCount2 = 91;
double intHolder = 0;

for (int i = 0; i <= intCount2; i++)
{
    if ((Math.Pow(i, 3) - 1) % intCount2 == 0)
    {
        if ((Math.Pow(i, 3) - 1) != 0)
        {
            Console.WriteLine(i);
            intHolder += i;
        }
    }
}
Console.WriteLine("Answer = " + intHolder);
Console.ReadLine();

Это работает для 91, нокогда я добавляю большое число с большим количеством нулей, это дает мне много ответов, которые, как я знаю, являются ложными.Я думаю, что это потому, что он настолько близок к 0, что просто округляется до 0. Есть ли способ узнать, что-то точно 0?Или моя логика неверна?

Я знаю, что мне нужна некоторая оптимизация, чтобы получить своевременный ответ, но я просто пытаюсь получить правильные ответы.

Answer 1

Позвольте мне обобщить ваши вопросы на два вопроса:

1) Что конкретно не так с этой программой?

2) Как определить, в чем проблема в программе?

Другие уже ответили на первую часть, но подведем итог:

Задача № 1: Math.Pow использует числа с плавающей запятой двойной точности, которые имеют точность до 15 знаков после запятой. Они не подходят для решения задач, которые требуют совершенной точности, включающей больших целых чисел . Если вы попытаетесь вычислить, скажем, 1000000000000000000 - 1, в два раза, вы получите 1000000000000000000, что является точным ответом до 15 десятичных знаков; это все, что мы гарантируем. Если вам нужен совершенно точный ответ для работы с большими числами, используйте long для результатов менее 10 миллиардов миллиардов или большой класс целочисленной математики в System.Numerics, который будет поставляться со следующей версией платформы.

Проблема № 2: Существуют гораздо более эффективные способы вычисления модульных показателей, которые не требуют генерации огромных чисел; используйте их.

Однако то, что мы имеем здесь, это ситуация "дай человеку рыбу". Что было бы лучше, так это научить вас ловить рыбу; научитесь отлаживать программу с помощью отладчика.

Если бы мне пришлось отлаживать эту программу, первым делом я бы переписал ее так, чтобы каждый шаг на этом пути был сохранен в локальной переменной:

double intCount2 = 91; 
double intHolder = 0; 

for (int i = 0; i <= intCount2; i++) 
{ 
    double cube = Math.Pow(i, 3) - 1;
    double remainder = cube % intCount2;
    if (remainder == 0) 
    { 
        if (cube != 0) 
        { 
            Console.WriteLine(i); 
            intHolder += i; 
        } 
    } 
} 

Теперь пройдитесь по нему в отладчике с примером, где вы знаете, что ответ неправильный, и найдите места, где ваши предположения нарушаются. Если вы это сделаете, вы быстро обнаружите, что 1000000 кубов минус 1 - это не 99999999999999999, а 1000000000000000000.

Так вот совет № 1: напишите код, чтобы в отладчике было легко проходить, и проверяйте каждый шаг в поисках того, который кажется неправильным.

Совет № 2: Обращайте внимание на тихие ноющие сомнения. Когда что-то выглядит унылым или есть что-то, чего вы не понимаете, исследуйте это, пока не поймете это.

Answer 2

Не вычислять полномочия по модулю n, используя Math.Pow; Вы, вероятно, испытаете проблемы переполнения среди других возможных проблем. Вместо этого вы должны вычислить их из первых принципов. Таким образом, чтобы вычислить куб целого числа i по модулю n, сначала уменьшите i по модулю n до некоторого целого числа j, чтобы i соответствовало j по модулю n и 0 <= j < n , Затем итеративно умножьте на j и уменьшите по модулю n после каждого умножения; чтобы вычислить куб, вы должны выполнить этот шаг дважды. Конечно, это нативный подход, но вы можете сделать его более эффективным, следуя классическому алгоритму возведения в степень, используя возведение в степень путем возведения в квадрат .

Также, что касается эффективности, отмечу, что вы без необходимости вычисляете Math.Pow(i, 3) - 1 дважды. Таким образом, как минимум, заменить

if ((Math.Pow(i, 3) - 1) % intCount2 == 0) {
    if ((Math.Pow(i, 3) - 1) != 0) {
        Console.WriteLine(i);
        intHolder += i;
    }
}

с

int cubed = Math.Pow(i, 3) - 1;
if((cubed % intCount2 == 0) && (cubed != 0)) {
    Console.WriteLine(i); 
    intHolder += i;
}

Answer 3

В Википедии есть статья о Модульном возведении в степень , которую вы можете найти информативной. IIRC, в Python он встроен. В C # нет, поэтому вам нужно реализовать его самостоятельно.

Answer 4

У меня нет решения вашей проблемы, но вот лишь совет:

• Не используйте числа с плавающей запятой для вычислений, которые включают только целые числа ... Тип int (Int32) явно недостаточно велик для ваших нужд, но long (Int64) должен хватит: наибольшее число, с которым вам придется манипулировать, будет (10 ^ 11 - 1) ^ 3, что меньше 10 ^ 14, что определенно меньше Int64.MaxValue. Преимущества:

  • все вычисления выполняются с 64-разрядными целыми числами, что должно быть достаточно эффективно на 64-разрядном процессоре
  • все результаты ваших расчетов точны, поскольку нет никаких приближений из-за внутреннего представления двойных чисел

• Не используйте Math.Pow для вычисления куба целого числа ... x*x*x так же просто и более эффективно, поскольку не требует преобразования в / из double. В любом случае, я не очень хорош в математике, но вам, вероятно, не нужно вычислять x ^ 3 ... проверить ссылки о модульном возведении в другие ответы

Answer 5

Ну, чего-то не хватает или опечатка ...

"intHolder1", предположительно, должен быть "intHolder", и для intCount2 = 91, чтобы получить 8, строка приращения должна быть: -

intHolder ++;