Оптимизиращ код за модулна аритметика - C ++, математика, оптимизация, модулно-аритметична

Опитвам се да изчисля по-долу израз за големи числа.

Тъй като стойността на този израз ще бъде много голяма, просто се нуждая от стойността на този израз модул някакъв първичен номер. Да предположим, че стойността на този израз е x и избирам премиерния номер 1000000007; Търся x % 1000000007.

Ето моя код.

#include<iostream>
#define MOD 1000000007
using namespace std;
int main()
{
unsigned long long A[1001];
A[2]=2;
for(int i=4;i<=1000;i+=2)
{
A[i]=((4*A[i-2])/i)%MOD;
A[i]=(A[i]*(i-1))%MOD;

while(1)
{
int N;
cin>>N;
cout<<A[N];
}
}

Но дори и тази много оптимизация е неуспешна за големи стойности от N. Например, ако N е 50, то е правилно 605552882, но това ми дава 132924730, Как мога да го оптимизирам допълнително, за да получим правилната мощност?

Забележка : Аз мисля само като N дори.

Отговори:

Когато правите модулна аритметика, няма таковафункциониране като разделение. Вместо това вземете модулния обрат на знаменателя и го умножете. Модулният инверсен се изчислява, като се използва удължения евклидов алгоритъм, открит от Етиен Безут през 1779 г .:

# return y such that x * y == 1 (mod m)
function inverse(x, m)
a, b, u := 0, m, 1
while x > 0
q, r := divide(b, x)
x, a, b, u := b % x, u, x, a - q * u
if b == 1 return a % m
error "must be coprime"

Най- divide функцията връща както коефициента, така и остатъка. Всички оператори на задачи, посочени по-горе, са едновременно задаване, при което всички дясни страни са изчислени първо, а всички ляво страни са присвоени едновременно. Можете да видите повече за модулната аритметика в Моят блог.

1. За начало не е необходимо модулно разделяне, формулата ви може да бъде пренаписана по следния начин:

   N! / ((N / 2)! ^ 2) = (1.2.3 ... N) / ((1.2.3 ... N / 2) * (1.2.3 ... N / 2)) = ((N / 2 + 1) ... N) / (1.2.3 ... N / 2))

   • добре сега разделяте по-голям брой от по-малките
   • така че можете да повторите резултата чрез умножаване на делителя и дивидента
   • така че резултатите от кабинния под имат подобна величина
   • всеки път и двата номера са неделими 2 ги смени наляво
   • това ще гарантира, че не преливат
   • ако сте в и на (N / 2)! отколкото да продължите мултиплицирането само за останалите.
   • всеки път, когато и двата последователни резултата се делят на нещо, което ги разделя
   • докато останеш с раздяла с 1
   • след това можете да се умножите с модулно аритметика до края нормално.

2. за по-напреднал подход вижте това.

   • N! и (N / 2)! се разлагат далеч по-далеч, отколкото изглежда на пръв поглед
   • Реших, че от известно време ...
   • Ето какво намерих: Бързо точен bigint факториален
   • накратко вашите условия N! и ((N / 2) 1) ^ 2 ще изчезне напълно.
   • само просто първо разпадане + 4N <-> 1N корекция ще напомня

решение:

I. (4N!)=((2N!)^2) . mul(i=all primes<=4N) of [i^sum(j=1,2,3,4,5,...4N>=i^j) of [(4N/(i^j))%2]]
II. (4N)!/((4N/2)!^2) = (4N)!/((2N)!^2)
----------------------------------------
I.=II. (4N)!/((2N)!^2)=mul(i=all primes<=4N) of [i^sum(j=1,2,3,4,5,...4N>=i^j) of [(4N/(i^j))%2]]

• единственото нещо е, че N трябва да се дели на 4 ... следователно 4N във всички отношения.
• ако имате N% 4! = 0 от решаването на N-N% 4 и резултатът е коригиран с грешката 1-3 числа.

Надявам се, че помага