Quesito (credo) semplice

[Wolowizard1]

Dati due numeri n = 111333222666 e m = 111333333111, stabilire quanti sono i divisori di m che non sono anche divisori di n.
Bisognerebbe calcolare il numero di divisori di m sottraendo poi (ovviamente XD) i divisori comuni ai due numeri... C'è qualche modo veloce veloce per farlo ? Calcolare i divisori col metodo 'classico' della scomposizione per numeri tanto grandi mi sembra troppo lungo come procedimento...

Per info è tratto dalle olimpiadi di matematica dell'università Tor Vergata di Roma, 17/12/11

[@melia]

Si può vedere abbastanza intuitivamente che m è divisibile per $111=3*37$ e per $1001$, facendo un paio di divisioni si determina la scomposizione in fattori di m che è $111333333111= 3*37*1001^3$, anche n è divisibile per $111$, quindi sia per 3 che per 37, ma non è divisibile per 1001, la scomposizione completa di n è più laboriosa, ma non è indispensabile.

[DKant10]

Per calcolare il numero dei divisori di un numero intero si procede in questo modo:

1) si fattorizza il numero
2) si scrive il numero come successione finita di potenze di primi (1 non compare nella fattorizzazione!)
3) si fa il prodotto delle potenze, aumentate di un'unità, dei primi che fattorizzano il numero.

Per darti un'idea di questo fatto prendi il numero $12=2^2*3^1$, i divisori sono:

$2^0*3^0$
$2^0*3^1$
$2^1*3^0$
$2^1*3^1$
$2^2*3^0$
$2^2*3^1$

Il numero $2$ compare fino alla seconda potenza, quindi i divisori di fattore $2$ hanno tre possibilità ($2^0$, $2^1$ e $2^2$)
Il numero $3$ compare fino alla prima potenza, quindi i divisori di fattore $3$ hanno due possibilità ($3^0, 3^1$)

Da qui è facile intuire che il numero totale di combinazioni è il prodotto delle singole possibilità:
in questo caso, come ci aspettiamo sono $3*2=6*$.

Applicando questi fatti al tuo problema, a meno di errori di calcolo, si ottiene:

$m=111333333111=3*7^3*11^3*13^3*37$ quindi il numero dei divisori è $2*4*4*4*2=256$

$n=111333222666= 2*3^2*17*37*59*166667$ quindi il numero dei divisori è $2*3*2*2*2*2=96$

Il fattore più grande di $n$ che è divisore di $m$ è $3*37$, quindi il numero di divisori comuni è $2*2=4$

Quindi, i divisori di $m$ che non sono anche divisori di $n$ è $256-4=252$

[giammaria2]

Do un modo per accelerare la scomposizione in fattori

$n=111*10^9+3*111*10^6+2*111*10^3+6*111=111(10^9+3*10^6+2*10^3+6)=$
$=111[10^6(10^3+3)+2(10^3+3)]=111(10^3+3)(10^6+2)$
ed ora bisognerebbe scomporre i singoli fattori, ma serve a poco e non è breve.

$m=111*10^9+3*111*10^6+3*111*10^3+111=111(10^9+3*10^6+3*10^3+1)=$
$=111(10^3+1)^3=111*1001^3=111*(7*11*13)^3$