Buonasera. Voi che metodo avete utilizzato per fare 100/100 in Decimal Fractions?
Io, per ogni numero da 1 a N, determino le cifre periodiche facendo le divisioni fino a quando trovo un resto che avevo già trovato in precedenza, però riesco a fare solo 50/100 perché con i testcase più complicati vado in timeout.
Grazie 
Ciao, io non ho ancora affrontato il problema però penso sia possibile trascurare a priori tutti gli n multipli di 2 o di 5 perché, a meno che non mi sbagli, la presenza di un antiperiodo non dovrebbe influenzare in alcun modo la lunghezza del periodo.
Mi spiego meglio:
sia d=2^a*5^b*c dove a,b,c sono numeri naturali tutti maggiori di 1 e c è diverso da 1 e c%2!=0 e c%5!=0, allora il periodo di 1/d ha la stessa lunghezza del periodo di 1/c.
Se non mi sbaglio su questa regola dovresti riuscire a escludere a priori più di metà dei numeri.
P.S.:
Ho appena fatto (fare) un paio di calcoli che mi hanno dato l’impressione che forse il periodo di 1/d (ponendo per la storia scritta sopra che d non è divisibile né per 2 né per 5) potrebbe essere ricavato nel seguente modo:
se d=a x b x c con a,b,c numeri primi distinti sembra che
lunghezza_periodo_di(1/d) = mcm(lunghezza_periodo_di(1/a), lunghezza_periodo_di(1/b),lunghezza_periodo_di(1/c)) e così via.
Inoltre sembra anche che se d=p^n dove n è un numero naturale qualsiasi e p è un numero primo valga la proprietà:
lunghezza_periodo_di(1/d)=lunghezza_periodo_di(1/p) x p^(n-1) anche se con le potenze di 3 sembra che il periodo sia lungo 3^(n-1).
Non sono minimamente sicuro delle ultime due cose e bisogna notare che mi sono messo a scrivere la domenica sera alle 23:30 pertanto se sono giuste è un miracolo, ma se il cielo è con me ed esistono delle regole queste potrebbero permettere di velocizzare tantissimo la soluzione.
Nota infatti che il periodo di 1/97 è lungo 96 cifre e quello di 1/97^3 invece ne conta 903’264 che non è altro che 96x97x97.
Per dare ulteriori consigli dovrei mettermi a risolvere seriamente il problema, spero di essere stato utile e chiaro e anche che se qualcuno qui, che di matematica ne sa più di me (il che non è difficile), ci riveli se queste proprietà sono reali e dimostrabili.
Poi vi sarebbe anche il dettaglio che il periodo di 1/d è lungo al più d-1 cifre (e questa non è una mia congettura ma lo si dimostra facilmente) pertanto, se il periodo di 1/d conta k cifre nessuna frazione 1/m con m<=k+1 potrà mai avere un periodo più lungo di quello di 1/d.
Ciao,
come ha appunto detto @Tredici il periodo di 1/d ha al più d-1 cifre e questo comporta che calcolare la lunghezza del periodo abbia complessità O(d) rendendo la soluzione finale O(N^2).
La soluzione lineare “corretta” fa uso di algebra modulare + numeri primi + fast exp + un po’ di dimostrazioni, se vuoi posso spiegartela non è troppo difficile.
L’altra soluzione lineare è più brutta e si basa sul fatto che avresti dovuto precomputare tutti i valori accorgendoti che fino a 10^6 i valori solo distanti al massimo 410 e quindi potevi restringere l’intervallo di ricerca tra N-410 e N-1.
Gentilmente la potresti spiegare a me?
Io stavo pensando di usare quanto scritto sopra per realizzare una sorta di crivello di Eratostene che associasse ad ogni numero tutti i suoi fattori primi in O( N(ln ln N)/2) (il fratto due è perché si possono trascurare a priori i numeri pari) e poi usare tecniche di memoizazione per calcolare solo all’occorrenza il periodo dei suoi fattori primi e determinarne cosi in O(1) (essendo ottimista) la lunghezza del periodo di ogni numero che non è multiplo né di 2 né di 5 usando un algoritmo per il mcm e affidandomi alle congetture che ho scritto ma non dimostrato.
Allora, partiamo con calcolare tutti i numeri primi in \mathcal O(N\log\log N), adesso abbiamo al più \frac{N}{\log N} numeri. I numeri che ci interessano a noi sono solo i full reptend primes, ovveri i numeri primi tali che se p è uno di questi allora la parte periodica di p è lunga p-1.
Prima di tutto bisogna capire come calcolare la lunghezza del periodo di un numero nella forma \frac{1}{d} con d generico, non necessariamente primo.
Supponiamo di voler isolare il periodo di lunghezza k, lo portiamo a sinistra della virgola moltiplicando \frac{1}{d} per 10^k e poi sottraiamo la parte decimale che sarà uguale a \frac{1}{d}. Quindi il periodo sarà \frac{10^k}{d} - \frac{1}{d}, raccogliendo abbiamo \frac{10^k-1}{d}. Essendo questo numero un intero vale la proprietà 10^k-1\equiv 0\pmod d che diventa 10^k\equiv 1\pmod d. Abbiamo ottenuto che un numero d ha k cifre periodiche se 10^k\equiv 1\pmod d.
A noi interessano i numeri primi tali che 10^{p-1}\equiv 1\pmod p. La potenza si può fare facilmente in \mathcal O(\log p), iterando per ogni numero primo e quindi \frac{N}{\log N} volte la soluzione finale avrà complessità \mathcal O\left(\frac {N}{\log N}\cdot \log N\right) e quindi \mathcal O(N) (a cui va aggiunto il crivello).
Spero di essera stato chiaro (viva MathJax), non è troppo difficile ma farselo venire in mente in gara è assurdo.
Aggiungo che un ragionamento analogo si poteva applicare anche all’altra soluzione con una cosa di questo tipo:
int cycle_length(int d)
{
int l=1;
for(int p=10; p!=1; l++)
{
p *= 10;
p %= d;
}
return l;
}
Ora grazie a @wil93 e al nuovo plugin ufficiale per la matematica di Discourse abbiamo di nuovo MathJax tra noi! 
Grazie mille per la spiegazione, solo un dubbio mi resta, è certo che il numero d<N tale che L(p), dove L(x) indica la lunghezza del periodo di 1/x, è un numero primo?
Teoricamente è possibile dimostrarlo, ma non mi ricordo come 
Comunque puoi verificare con degli assert e otterrai che ogni numero d è primo e ha un ciclo di lunghezza d-1.