Numeri di Figonacci

Dopo l’ultimo seminario di teoria dei numeri, Giorgio è rimasto affascinato dallo studio della sequenza dei numeri di Fibonacci.
Pertanto, per non essere da meno, introduce una nuova sequenza di numeri secondo lui ancora più interessante: i numeri di Figonacci.
Come per i loro quasi-omonimi, l’(n+1)-esimo numero di Figonacci G_n+1 si calcola a partire dai precedenti (eccezion fatta per i primi due numeri di Figonacci, che sono valori fissati a G₀=−1 e G₁=0).

La regola che stabilisce il valore di G_N+1, tuttavia, è diversa da quella dei numeri di Fibonacci: G_N+1 è pari alla somma di tutte le possibili differenze tra il numero di Figonacci immediatamente precedente e quelli ancora prima.

In formule:

I primi numeri che si ottengono da questa sequenza sono quindi −1, 0, 1, 3, 9, . . . ed è facile vedere che crescono molto rapidamente.
Ma questo non è un problema per Giorgio, che è interessato ad usarli per problemi di teoria dei numeri, e a cui quindi interessa soltanto il valore modulo M di questi numeri.

Aiuta la sua ricerca calcolando il valore dell’N-esimo numero di Figonacci G_N modulo M.

Dati di input

Il file input.txt è composto da un’unica riga contenente i due numeri interi N ed M.

Dati di output

Il file output.txt è composto da un’unica riga contenente un unico intero, la risposta a questo problema.

Assunzioni

• 2 ≤ N ≤ 1000000
• 2 ≤ M ≤ 40 000.

Esempi di input/output

input.txt	output.txt
3 10	3
4 3	0
5 9	6

Spiegazione

• Nel primo caso di esempio, G3=3 che modulo 10 resta 3.
• Nel secondo caso di esempio, G4=9 che modulo 3 fa 0.
• Nel terzo caso di esempio, G5=33 che modulo 9 fa 6.

Note

L’operazione di modulo si calcola con l’operatore % in C/C++.
Notare che può dare risultati non corretti se l’argomento è negativo (il che può succedere per diversi motivi).
Un modo per risolvere questo problema è usare il seguente codice:

(G_N % M + M) % M

L’operazione di modulo, inoltre, ha le seguenti proprietà (molto utili per evitare integer overflow quando si vogliono calcolare numeri molto grandi):

• (A+B) mod M = (A mod M + B mod M) mod M
• (A·B) mod M = (A mod M · B mod M) mod M

---

/*
    www.valcon.it
    Competenze Digitali - Numeri di Figonacci 
*/

#include

long figonacci[NMAX];

int main()
{
	long N, M;
	long G2,G1,S0;
	
	FILE* fin =fopen( "input.txt","r");
	FILE* fout=fopen("output.txt","w");
	
	fscanf(fin, "%ld%ld", &N, &M);
	
	     if(N == 0) G2=M-1;
	else if(N == 1) G2=0;
	else
	{
        G1=0;
        S0=-1;
		for(long i=2; i <= N; i++)
	    {
		    G2=(((i-1)%M)*G1-S0+M)%M;
		    S0=(S0+G1)%M;
		    G1=G2;
	    }
	}
		
	fprintf(fout, "%ld", G2);	
	return 0;
}