Un bruco mangia tutti i multipli del suo "passo di salto" j, quindi se fosse solo, ogni bruco mangerebbe foglie floor(n/j).
Ora devi capire quali foglie hai contato più volte. Ad esempio se contate tutte le foglie divisibili per 2 per il primo bruco, allora non dovete contare le foglie per il secondo bruco, che salta 4 per 4.
Per due voci, questi numeri contati due volte sono i multipli del least common multiple di entrambi gli articoli e ci sono floor(n/lcm(j,j')) di quelli.
Si noti che per tre termini, se si esegue questo calcolo, è possibile rimuovere alcuni elementi due volte: prendiamo 28 nell'esempio. Sarà consumato dal bruco con passaggio 7, ma conteggiato per entrambi gli altri (perché 28% 4 == 28% 2 == 0), quindi è necessario aggiungere i multipli che sono stati rimossi più volte: floor(n/lcm(j,j',j"))
Puoi vedere uno schema qui, è the inclusion-exclusion principle. La formula generale segue:
Let Aj essere le foglie mangiate da un bruco con il passaggio salto j (se fosse da solo). Quindi per J un set di diversi set di jump di capterpillar, A J è l'insieme di foglie mangiate da tutti questi bruchi.
dobbiamo anche definire il minimo comune multiplo di un insieme come il minimo comune multiplo di tutti gli elementi dell'insieme, così possiamo scrivere lcm(J).
Il [n] nella formula di inclusione-esclusione è l'insieme di salti di caterpillar considerati, quindi nel tuo caso [2,4,7], e iteriamo su tutti i sottoinsiemi di esso. |J| è la dimensione del sottoinsieme e | A J | è la dimensione del numero di foglie che ogni bruco in J potrebbe mangiare, quindi otteniamo | A J | = floor(n/lcm(J)).
Ora avete una somma di 2 c termini *, poiché questo è il numero di sottoinsiemi dei caterpillar c. Tieni presente che puoi risparmiare un po 'di tempo salvando i multipli meno comuni invece di ricalcolarli da zero.
Lascio scrivere il codice effettivo "come esercizio", come alcuni amano dire: è in pratica iterando su sottoinsiemi e calcolando i multipli meno comuni, quindi mettendoli tutti insieme nella somma sopra.
Questo ti dà il numero totale di foglie mangiate. Ottenere quelli non mangiati da qui è banale.
Se lo facciamo su un piccolo esempio (per essere in grado di controllare), con 0 il suolo, 1..24 le foglie, e [2,3,4] le fasi di salto bruco.
Le uniche foglie sopravvissute saranno {1, 5, 7, 11, 13, 17, 19, 23}: rimuovendo tutti i numeri pari e tutti i numeri divisibili per 3. Cioè, ci aspettiamo che la risposta sia 8.
- Primo turno: i sottoinsiemi di dimensioni 1.
- Caterpillar
j=2 sarebbero, da solo, mangiare 24/2 = 12 foglie
- Caterpillar
j=3 sarebbe, da solo, mangiare 24/3 = 8 foglie
- Caterpillar
j=4 sarebbe, da solo, mangiare 24/4 = 6 foglie
- Secondo turno: i sottoinsiemi di dimensioni 2.
- Caterpillar
j=2 e j=3 sarebbero entrambi piace mangiare 24/6 = 4 foglie: {6, 12, 18, 24}
- Caterpillar
j=3 e j=4 sarebbero entrambi piace mangiare 24/12 = 2 foglie di: {12, 24}
- Caterpillar
j=4 e j=2 sarebbero entrambi piace mangiare 24/4 = 6 foglie: tutte quelli mangiati da 4 sono mira da 2
- terzo turno: sottoinsiemi di dimensioni 3: tutti i bruchi insieme
- Tutti vorrebbero mangiare 24/LCM (2,3,4) = 24/12 = 2 foglie di: { 12, 24}.
- Fase finale: 12 + 8 + 6 - 4 - 26 + 2 = 26 - 12 + 2 = 16 foglie vengono mangiate
Quindi 24 - 16 = 8 foglie rimangono.
* naturalmente questo è uno scenario peggiore. Si spera che itererai su sottoinsiemi di dimensioni crescenti, e non appena il minimo comune multiplo di un sottoinsieme J è maggiore di n, puoi ignorare tutti i superset di quel J. In particolare, se tutti i sottoinsiemi di una dimensione k hanno un lcm più grande di n, puoi interrompere l'iterazione.
Qualunque foglia il cui numero non è un multiplo di uno qualsiasi dei numeri della matrice proposta è lasciato non vengono consumate. –
È possibile utilizzare il [principio di inclusione-esclusione] (http://en.wikipedia.org/wiki/Inclusione%E2%80%93exclusion_principle) – anatolyg
@ user1990169 Sì, ho capito che il problema si riduce alla dichiarazione che hai appena ha dato. Quindi la domanda converte in qual è il modo migliore per trovare numeri che non siano multipli di nessuno dei numeri. – Hoxeni