[C++] Suma silni

[mario765i]

Cześć! Mam do napisania program w języku c++ (używam CodeBlocks) takiej treści: Dana jest liczba m, obliczyć resztę z dzielenia liczby \(\displaystyle{ x = 1! + 2! + 3! + 4! + 5! + ... + 999999999! + 1000000000!}\) przez m.
Na wejściu należy podać liczbę całkowitą dodatnią \(\displaystyle{ m (m \le 1000)}\). A na wyjściu oczekuję reszty z dzielenia liczby x przez liczbę m.

Oto napisany przeze mnie program:

Kod: Zaznacz cały

#include<iostream>
using namespace std;

int silnia(int p)
{
	if(p==1)
		return 1;
	else
	{
		return p*silnia(p-1);
	}

}
int main()
{
	int l=0;
	int m;
	int wynik;

	cin>>m;

	for(int i=1;i<m;i++)
	{
		l=l+silnia(i);
	}

	wynik=l%m;
	if(wynik<0)
	{
	    wynik+=m;
	}

	cout<<wynik;
	return 0;
}

Niby powinien działać poprawnie, ale po wysłaniu go na sprawdzarkę themis, otrzymuję komunikat "wrong answer" i nie wiem gdzie jest błąd. Może mógłby mi ktoś poprawić ten program, aby działał jak powinien.

[Zordon]

zmienna int nie pomieści tak dużych liczb, zresztą żaden standardowy typ zmiennej tego nie pomieści, musisz pomyśleć nad innym rozwiązaniem. W szczególności przyjrzyj się tożsamościom:
\(\displaystyle{ (a+b) \mbox{ mod m}=((a\mbox{ mod m})+(b\mbox{ mod m}))\mbox{ mod m}}\)
\(\displaystyle{ (a\cdot b) \mbox{ mod m}=((a\mbox{ mod m})\cdot(b\mbox{ mod m}))\mbox{ mod m}}\)

[norwimaj]

A gdy już zastosujesz się do uwagi Zordona, to pomyśl jeszcze o złożoności. Liczenie silni za każdym razem od początku nie jest najlepszym pomysłem.

[Zordon]

poza tym czemu iterujesz do \(\displaystyle{ m}\) skoro wcześniej napisałeś że suma ma się kończyć na 1000000000

[norwimaj]

Bardzo dobrze, że do \(\displaystyle{ m}\). Pozostałe składniki są podzielne przez \(\displaystyle{ m}\), więc nie wpływają na wynik.

[mario765i]

Po waszych wskazówkach napisałem program od początku.
Oto nowy kod:

Kod: Zaznacz cały

#include<iostream>
using namespace std;

int main()
{
    int m, i;
    int x=1, w=0;

    cin >> m;

    for(i=1; i<m; i++)
    {
        x=(x*i)%m;
        w=(w+x)%m;
    }

    cout << w << endl;

    return 0;
}

Co o nim myślicie? Powinien już działać poprawnie, czy jeszcze nie?

[norwimaj]

Nie sprawdzałem czy daje poprawne wyniki, ale wygląda dobrze.

Można też to zrobić trochę inaczej, w zależności od tego, co komu się bardziej podoba.

Kod: Zaznacz cały

#include<iostream>
using namespace std;

int main()
{
    int m, i;
    int w=0;

    cin >> m;

    for(i=m; i>1; i--) w=(w*i+1)%m;

    cout << w << endl;

    return 0;
}

[mario765i]

Skoro wygląda dobrze, to dobrze. Dzięki za pomoc.