Решение 1 ^ 1 + 2 ^ 2 + 3 ^ 3 + & hellip; N ^ N [дубликат]
По вопросу «что мне делать с этим» может быть много ответов.
Более «формальный» способ предотвращения таких ошибок при разработке применяя дизайн по контракту в вашем коде. Это означает, что при разработке вы должны установить инварианты класса и / или даже предпосылки для функции и .
Короче говоря, инварианты класса гарантируют, что в вашем классе будут некоторые ограничения, которые не будут нарушены при нормальном использовании (и, следовательно, класс будет not получить в несогласованном состоянии). Предпосылки означают, что данные, данные как входные данные для функции / метода, должны соответствовать установленным ограничениям и никогда не нарушать их, а постулаты означают, что вывод функции / метода должен соответствовать установленным ограничениям снова не нарушая их. Условия контракта никогда не должны нарушаться во время выполнения программы без ошибок, поэтому дизайн по контракту проверяется на практике в режиме отладки, а отключен в выпусках , чтобы максимизировать развитую производительность системы.
Таким образом, вы можете избежать случаев NullReferenceException, которые являются результатом нарушения установленных ограничений. Например, если вы используете свойство объекта X в классе, а затем попытаетесь вызвать один из его методов, а X имеет нулевое значение, то это приведет к NullReferenceException:
public X { get; set; }
public void InvokeX()
{
X.DoSomething(); // if X value is null, you will get a NullReferenceException
}
Но если вы установите «свойство X никогда не должно иметь нулевого значения» в качестве предпосылки для метода, вы можете предотвратить описанный ранее сценарий:
//Using code contracts:
[ContractInvariantMethod]
protected void ObjectInvariant ()
{
Contract.Invariant ( X != null );
//...
}
По этой причине Код Контракт существует для приложений .NET.
В качестве альтернативы дизайн по контракту может быть применен с использованием утверждений .
ОБНОВЛЕНИЕ: Стоит отметить, что этот термин был придуман Бертраном Майером в связи с его дизайном языка программирования Эйфеля .
6 ответов
Две ноты:
(a + b + c) % m
эквивалентно
(a % m + b % m + c % m) % m
и
(a * b * c) % m
эквивалентно
((a % m) * (b % m) * (c % m)) % m
В результате вы можете рассчитать каждый термин, используя рекурсивную функцию в O (log p ):
int expmod(int n, int p, int m) {
if (p == 0) return 1;
int nm = n % m;
long long r = expmod(nm, p / 2, m);
r = (r * r) % m;
if (p % 2 == 0) return r;
return (r * nm) % m;
}
И элементы суммы, использующие цикл for:
long long r = 0;
for (int i = 1; i <= n; ++i)
r = (r + expmod(i, i, m)) % m;
Этот алгоритм O ( n log n ).
-
1Для небольших чисел я делаю то же самое. Но его убивают за n = 1000000 и m = 200000. Я включил код – user 1 October 2009 в 11:01
-
2Я полагаю, что в этих уравнениях вам нужен еще один «mod»: (a% m + b% m + c% m)% m 'и' (a% m) * (b% m) * (c% m) % m '. – Groo 1 October 2009 в 11:06
-
3Гроо: Да, сделал это в коде, пропущенный в уравнениях. Благодарю. Исправлена. – Mehrdad Afshari 1 October 2009 в 11:08
-
4@rahul: ваш внутренний j-цикл работает в O (i). Функция Мехрдада выполняется в O (log i). Замените свою внутреннюю петлю вызовом функции Мехрдада, и вы получите большое ускорение. – dave4420 1 October 2009 в 11:10
-
5@rahul. В случае n = 1000 и m = 2000, результат 1000 ^ 1000% 2000 до (1000 ^ 2% 2000) ^ 500% 2000. – user172818 1 October 2009 в 11:11
Здесь вас убивают:
for(j=1;j<=i;j++)
t=((long long)t*i)%m;
Экспоненты mod m могут быть реализованы с использованием метода чисел квадратов.
n = 10000;
m = 20000;
sqr = n;
bit = n;
sum = 0;
while(bit > 0)
{
if(bit % 2 == 1)
{
sum += sqr;
}
sqr = (sqr * sqr) % m;
bit >>= 2;
}
Вы можете посмотреть мой ответ на этот пост . Реализация там немного глючит, но идея есть. Основная стратегия состоит в том, чтобы найти х так, что n ^ (x-1) & lt; m и n ^ x & gt; m и многократно уменьшать n ^ n% m до (n ^ x% m) ^ (n / x) * n ^ (п% х)% м. Я уверен, что эта стратегия работает.
Я не могу добавить комментарий, но для китайской теоремы о остатках см. http://mathworld.wolfram.com/ChineseRemainderTheorem.html формулы (4) - (6).
-
1
В последнее время я столкнулся с похожим вопросом: мой «n» равен 1435, «m» равен 10 ^ 10. Вот мое решение (C #):
ulong n = 1435, s = 0, mod = 0;
mod = ulong.Parse(Math.Pow(10, 10).ToString());
for (ulong i = 1; i <= n;
{
ulong summand = i;
for (ulong j = 2; j <= i; j++)
{
summand *= i;
summand = summand % mod;
}
s += summand;
s = s % mod;
}
В конце '' равно требуемому числу.
Я думаю, вы можете использовать теорему Эйлера, чтобы избежать некоторого возведения в степень, так как phi (200000) = 80000. Теорема о китайском остатке может также помочь, поскольку она уменьшает модулю.
-
1Это действительно звонит, но я боюсь, что вам придется объяснять. Кроме того, iirc, вычисление phi не является тривиальным. – Kobi 1 October 2009 в 11:26
-
2Вы должны вычислить phi только один раз. Теорема Эйлера гласит, что a ^ phi (b) = 1 mod b, если (a, b) = 1. Тогда вы можете упростить a ^ c mod b до формы a ^ c 'mod b, где c' & lt; phi (b). – user 1 October 2009 в 11:35
-
3Jaska: Это не имеет значения здесь. Что делать, если
(a,b) != 1? – Mehrdad Afshari 1 October 2009 в 11:43 -
4Совет. Попробуйте отредактировать свой ответ. Разрабатывать. Опишите и объясните предложенный вами алгоритм. Попробуйте опубликовать код. Ссылка на Википедию. Кроме того, не является ли китайская теорема о остатках, используемая для набора уравнений? – Kobi 1 October 2009 в 12:04
-
5Теорема Эйлера и теорема о китайском напоминании легко найти, и они оба (в совокупности) совершенно уместны здесь - используйте теорему Эйлера для вычисления суммы мод каждой главной степени в m и используйте CRT для их объединения. – ShreevatsaR 1 October 2009 в 23:52