Пари з повним квадратом#12428

Пари з повним квадратом (Розбір)

Будь-яке натуральне число єдиним чином можна подати у вигляді $i = k \cdot x^{2}$ i = k \cdot x^2, де $k$ вільне від квадратів, тобто не ділиться на жоден квадрат простого числа. Число $k$ називається вільною від квадратів частиною числа $i$ . Позначимо її $s f [i]$ . Наприклад:

$6 = 2 \cdot 3$ 6 = 2 \cdot 3, тому $s f [6] = 6$ sf[6] = 6;
$12 = 2^{2} \cdot 3$ 12 = 2^2 \cdot 3, тому $s f [12] = 3$ sf[12] = 3;

Теорема. Добуток $a \cdot b$ a \cdot b є повним квадратом тоді і тільки тоді, коли $s f [a] = s f [b]$ sf[a] = sf[b].

Доведення. Нехай

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

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

де $k_{1}$ k_1 і $k_{2}$ k_2 вільні від квадратів. Тоді

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

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

Цей вираз є повним квадратом тоді і тільки тоді, коли повним квадратом є $k_{1} k_{2}$ k_1k_2. Але числа $k_{1}$ k_1 і $k_{2}$ k_2 вільні від квадратів. Отже, $k_{1} k_{2}$ k_1k_2 є повним квадратом лише якщо $k_{1} = k_{2}$ k_1 = k_2.

Зведення до підрахунку груп. З теореми випливає, що числа від $1$ до $n$ розбиваються на групи за значенням $s f [i]$ , і пара $(a, b)$ підходить ( $a \cdot b$ a \cdot b є точним квадратом) тоді і тільки тоді, коли $a$ і $b$ лежать в одній групі.

Нехай $c n t [k]$ дорівнює кількості чисел $i (1 \leq i \leq n)$ i~(1 \le i \le n), для яких $s f [i] = k$ sf[i] = k. Для його обчислення достатньо для кожного $i$ виконати операцію $c n t [s f [i]] + +$ cnt[sf[i]]++.

Якщо в групі $m$ чисел, то вона дає

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

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

пар. Відповідь дорівнює сумі по всіх групах:

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

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

Найменший простий дільник. Для швидкого обчислення $s f [i]$ введемо масив $s p f [i]$ , що дорівнює найменшому простому дільнику числа $i$ . Наприклад:

Масив $s p f$ обчислюється модифікованим решетом Ератосфена: при обробці простого $p$ значення $s p f [j] = p$ spf[j] = p присвоюється кожному кратному $j$ числа $p$ , для якого воно ще не було встановлено.

Маючи масив $s p f$ , можна обчислити квадрат-вільну частину кожного числа $s f [i]$ . Нехай $p$ — найменший простий дільник числа $i$ ( $s p f [i] = p$ spf[i] = p). Розглянемо два випадки:

$p$ зустрічається в розкладі числа $i$ щонайменше два рази. Це означає, що число $i$ ділиться на $p^{2}$ p^2. Два однакові прості множники $p$ утворюють повний квадрат, тому їх можна виключити з квадрат-вільної частини:

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

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

Наприклад:

$s f [12] = s f [3]$ sf[12] = sf[3], оскільки $s p f [12] = 2$ spf[12] = 2 і $12$ ділиться на $2^{2}$ 2^2;
$s f [45]$ = $s f [5]$ , оскільки $s p f [45] = 3$ spf[45] = 3 і $45$ ділиться на $3^{2}$ 3^2;

$p$ зустрічається в розкладі числа $i$ лише один раз. Тому множник $p$ повинен залишитися в квадрат-вільній частині:

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

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

Наприклад:

$s f [30] = s f [15] \cdot 2$ sf[30] = sf[15] \cdot 2, оскільки $s p f [30] = 2$ spf[30] = 2 і $30$ не ділиться на $2^{2}$ 2^2;
$s f [18] = s f [9] \cdot 2$ sf[18] = sf[9] \cdot 2, оскільки $s p f [18] = 2$ spf[18] = 2 і $18$ не ділиться на $2^{2}$ 2^2;

Приклад

Обчислимо відповідь для $n = 10$ n = 10.

i	розклад на множники	квадрат-вільна частина
$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$

Групуємо числа в масиві $c n t$ за $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)

Відповідь дорівнює

\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

Реалізація алгоритму

Оголосимо константи та масиви.

#define MAXN 1000000
#define MOD 1000000007
int spf[MAXN + 1];     // мінімальний простий дільник числа
int sf[MAXN + 1];      // квадрат-вільні частини числа
int cnt[MAXN + 1];     // кількість чисел із заданим sf

Читаємо вхідне значення $n$ .

scanf("%d", &n);

Застосовуючи метод решета Ератосфена, заповнюємо масив $s p f$ :

$s p f [i]$ повинно містити мінімальний простий дільник числа $i$

Спочатку вважаємо, що кожне число ділиться саме на себе. Але це тимчасово.

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

У змінній $i$ перебираємо числа від $2$ до $n$ \sqrt{n}.

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

Якщо число $i$ просте, у змінній $j$ перебираємо числа $i^{2}, i^{2} + i, i^{2} + 2 i, ...$ i^2, i^2 + i, i^2 + 2i, ... . Усі ці числа мають простий дільник $i$ (оскільки $s p f [i] = i$ spf[i] = i). Якщо $s p f [j] = j$ spf[j] = j, то оновлюємо мінімальний простий дільник для числа $j$ .

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

Для кожного числа $i$ обчислюємо його вільну від квадратів частину. Результат заносимо в $s f [i]$ .

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

Змінна $p$ містить найменший простий дільник числа $i$ .

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

Якщо $i$ ділиться на $p^{2}$ p^2, то $s f [i] = s f [i / p^{2}]$ sf[i] = sf[i / p^2].

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

Якщо $i$ не ділиться на $p^{2}$ p^2 (але ділиться на $p$ ), то $s f [i] = s f [i / p] \cdot p$ sf[i] = sf[i / p] \cdot p.

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

Групуємо числа за їхньою квадрат-вільною частиною.

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

Обчислюємо відповідь — шукану кількість пар.

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

Виводимо відповідь.

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