Coppie con quadrato perfetto#12428

Coppie con quadrato perfetto (Editoriale)

Qualsiasi numero naturale è rappresentabile in modo unico nella forma $i = k \cdot x^{2}$ i = k \cdot x^2, dove $k$ è libero da quadrati, cioè non è divisibile per il quadrato di alcun numero primo. Il numero $k$ si chiama parte libera da quadrati del numero $i$ . Lo indichiamo con $s f [i]$ . Ad esempio:

$6 = 2 \cdot 3$ 6 = 2 \cdot 3, quindi $s f [6] = 6$ sf[6] = 6;
$12 = 2^{2} \cdot 3$ 12 = 2^2 \cdot 3, quindi $s f [12] = 3$ sf[12] = 3;

Teorema. Il prodotto $a \cdot b$ a \cdot b è un quadrato perfetto se e solo se $s f [a] = s f [b]$ sf[a] = sf[b].

Dimostrazione. Siano

a = k_{1} \cdot x_{2}, b = k_{2} \cdot y_{2},

a = k_1 \cdot x_2, \\ b = k_2 \cdot y_2,

dove $k_{1}$ k_1 e $k_{2}$ k_2 sono liberi da quadrati. Allora

a * b = k_{1} k_{2} \cdot (x y)^{2}

a * b = k_1k_2 \cdot (xy)^2

Questa espressione è un quadrato perfetto se e solo se $k_{1} k_{2}$ k_1k_2 è un quadrato perfetto. Ma i numeri $k_{1}$ k_1 e $k_{2}$ k_2 sono liberi da quadrati. Di conseguenza $k_{1} k_{2}$ k_1k_2 è un quadrato perfetto solo se $k_{1} = k_{2}$ k_1 = k_2.

Riduzione al conteggio dei gruppi. Dal teorema segue che i numeri da $1$ a $n$ si suddividono in gruppi in base al valore $s f [i]$ , e la coppia $(a, b)$ è valida ( $a \cdot b$ a \cdot b è un quadrato perfetto) se e solo se $a$ e $b$ appartengono allo stesso gruppo.

Sia $c n t [k]$ uguale al numero di numeri $i (1 \leq i \leq n)$ i~(1 \le i \le n) per cui $s f [i] = k$ sf[i] = k. Per calcolarlo è sufficiente eseguire per ogni $i$ l'operazione $c n t [s f [i]] + +$ cnt[sf[i]]++.

Se in un gruppo ci sono $m$ numeri, esso dà

C_{m}^{2} = \frac{m \cdot ( m - 1 )}{2}

C_m^2 = \frac{m \cdot (m - 1)}{2}

coppie. La risposta è uguale alla somma su tutti i gruppi:

k \sum \frac{c n t [ k ] \cdot ( c n t [ k ] - 1 )}{2}

\sum_k \frac{cnt[k] \cdot(cnt[k] - 1)}{2}

Divisore primo minimo. Per calcolare rapidamente $s f [i]$ introduciamo un array $s p f [i]$ , uguale al minimo divisore primo del numero $i$ . Ad esempio:

L'array $s p f$ viene calcolato con un crivello di Eratostene modificato: durante l'elaborazione del numero primo $p$ , il valore $s p f [j] = p$ spf[j] = p viene assegnato a ogni multiplo $j$ del numero $p$ , per il quale non è ancora stato impostato.

Avendo l'array $s p f$ , si può calcolare la parte libera da quadrati di ogni numero $s f [i]$ . Sia $p$ il minimo divisore primo del numero $i$ ( $s p f [i] = p$ spf[i] = p). Consideriamo due casi:

$p$ compare nella scomposizione del numero $i$ almeno due volte. Questo significa che il numero $i$ è divisibile per $p^{2}$ p^2. Due fattori primi uguali $p$ formano un quadrato perfetto, quindi possono essere esclusi dalla parte libera da quadrati:

s f [i] = s f [i / p^{2}]

sf[i] = sf[i / p^2]

Ad esempio:

$s f [12] = s f [3]$ sf[12] = sf[3], poiché $s p f [12] = 2$ spf[12] = 2 e $12$ è divisibile per $2^{2}$ 2^2;
$s f [45]$ = $s f [5]$ , poiché $s p f [45] = 3$ spf[45] = 3 e $45$ è divisibile per $3^{2}$ 3^2;

$p$ compare nella scomposizione del numero $i$ solo una volta. Quindi il fattore $p$ deve rimanere nella parte libera da quadrati:

s f [i] = s f [i / p] \cdot p

sf[i] = sf[i / p] \cdot p

Ad esempio:

$s f [30] = s f [15] \cdot 2$ sf[30] = sf[15] \cdot 2, poiché $s p f [30] = 2$ spf[30] = 2 e $30$ non è divisibile per $2^{2}$ 2^2;
$s f [18] = s f [9] \cdot 2$ sf[18] = sf[9] \cdot 2, poiché $s p f [18] = 2$ spf[18] = 2 e $18$ non è divisibile per $2^{2}$ 2^2;

Esempio

Calcoliamo la risposta per $n = 10$ n = 10.

i	scomposizione in fattori	parte libera da quadrati
$1$	$1$	$1$
$2$	$2$	$2$
$3$	$3$	$3$
$4$	$1 * 2^{2}$ 1 * 2^2	$1$
$5$	$5$	$5$
$6$	$2 * 3$ 2 * 3	$6$
$7$	$7$	$7$
$8$	$2 * 2^{2}$ 2 * 2^2	$2$
$9$	$1 * 3^{2}$ 1 * 3^2	$1$
$10$	$2 * 5$ 2 * 5	$10$

Raggruppiamo i numeri nell'array $c n t$ in base a $s f [i]$ .

$c n t [1] = 3 : (1, 4, 9)$ cnt[1] = 3: (1, 4, 9)	$c n t [6] = 1 : (6)$ cnt[6] = 1: (6)
$c n t [2] = 2 : (2, 8)$ cnt[2] = 2: (2, 8)	$c n t [7] = 1 : (7)$ cnt[7] = 1: (7)
$c n t [3] = 1 : (3)$ cnt[3] = 1: (3)	$c n t [8] = 0 : ()$ cnt[8] = 0: ()
$c n t [4] = 0 : ()$ cnt[4] = 0: ()	$c n t [9] = 0 : ()$ cnt[9] = 0: ()
$c n t [5] = 1 : (5)$ cnt[5] = 1: (5)	$c n t [10] = 1 : (10)$ cnt[10] = 1: (10)

La risposta è uguale a

\frac{c n t [ 1 ] \cdot ( c n t [ 1 ] - 1 )}{2} + \frac{c n t [ 2 ] \cdot ( c n t [ 2 ] - 1 )}{2} = \frac{3 \cdot 2}{2} + \frac{2 \cdot 1}{2} = 3 + 1 = 4

\frac{cnt[1] \cdot (cnt[1] - 1)}{2} + \frac{cnt[2] \cdot (cnt[2] - 1)}{2} = \frac{3 \cdot 2}{2} + \frac{2 \cdot 1}{2} = 3 + 1 = 4

Implementazione dell'algoritmo

Dichiariamo le costanti e gli array.

#define MAXN 1000000
#define MOD 1000000007
int spf[MAXN + 1];     // divisore primo minimo del numero
int sf[MAXN + 1];      // parti libere da quadrati del numero
int cnt[MAXN + 1];     // quantità di numeri con un dato sf

Leggiamo il valore di input $n$ .

scanf("%d", &n);

Applicando il metodo del crivello di Eratostene, riempiamo l'array $s p f$ :

$s p f [i]$ deve contenere il divisore primo minimo del numero $i$

Inizialmente supponiamo che ogni numero sia divisibile per se stesso. Ma questo è temporaneo.

for (i = 1; i <= n; i++) spf[i] = i;

Nella variabile $i$ scorriamo i numeri da $2$ a $n$ \sqrt{n}.

for (i = 2; i * i <= n; i++)
{
  if (spf[i] == i)
  {

Se il numero $i$ è primo, nella variabile $j$ scorriamo i numeri $i^{2}, i^{2} + i, i^{2} + 2 i, ...$ i^2, i^2 + i, i^2 + 2i, ... . Tutti questi numeri hanno il divisore primo $i$ (poiché $s p f [i] = i$ spf[i] = i). Se $s p f [j] = j$ spf[j] = j, allora aggiorniamo il divisore primo minimo per il numero $j$ .

    for (j = i * i; j <= n; j += i)
      if (spf[j] == j) spf[j] = i;
  }
}

Per ogni numero $i$ calcoliamo la sua parte libera da quadrati. Il risultato lo inseriamo in $s f [i]$ .

sf[1] = 1;
for (i = 2; i <= n; i++)
{

La variabile $p$ contiene il minimo divisore primo del numero $i$ .

  p = spf[i];
  x = i / p;

Se $i$ è divisibile per $p^{2}$ p^2, allora $s f [i] = s f [i / p^{2}]$ sf[i] = sf[i / p^2].

  if (x % p == 0)
    sf[i] = sf[x / p];

Se $i$ non è divisibile per $p^{2}$ p^2 (ma è divisibile per $p$ ), allora $s f [i] = s f [i / p] \cdot p$ sf[i] = sf[i / p] \cdot p.

  else
    sf[i] = sf[x] * p;
}

Raggruppiamo i numeri in base alla loro parte libera da quadrati.

for (i = 1; i <= n; i++)
  cnt[sf[i]]++;

Calcoliamo la risposta — il numero di coppie cercato.

res = 0;
for (i = 1; i <= n; i++)
  if (cnt[i] >= 2)
    res = (res + cnt[i] * (cnt[i] - 1) / 2) % MOD;

Stampiamo la risposta.

printf("%lld\n", res);