Tam kvadratla cütlər#12428

Tam kvadratla cütlər (Həll təhlili)

İstənilən natural ədəd yeganə şəkildə $i = k \cdot x^{2}$ i = k \cdot x^2 kimi göstərilə bilər, burada $k$ kvadratsızdır, yəni heç bir sadə ədədin kvadratına bölünmür. $k$ ədədi $i$ ədədinin kvadratsız hissəsi adlanır. Onu $s f [i]$ ilə işarə edək. Məsələn:

$6 = 2 \cdot 3$ 6 = 2 \cdot 3, buna görə $s f [6] = 6$ sf[6] = 6;
$12 = 2^{2} \cdot 3$ 12 = 2^2 \cdot 3, buna görə $s f [12] = 3$ sf[12] = 3;

Teorem. $a \cdot b$ a \cdot b hasili tam kvadratdır ancaq və ancaq $s f [a] = s f [b]$ sf[a] = sf[b] olduqda.

İsbat. Tutaq ki,

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

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

burada $k_{1}$ k_1 və $k_{2}$ k_2 kvadratsızdır. Onda

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

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

Bu ifadə tam kvadratdır ancaq və ancaq $k_{1} k_{2}$ k_1k_2 tam kvadrat olduqda. Lakin $k_{1}$ k_1 və $k_{2}$ k_2 ədədləri kvadratsızdır. Deməli, $k_{1} k_{2}$ k_1k_2 tam kvadrat olar yalnız $k_{1} = k_{2}$ k_1 = k_2 olduqda.

Qrupların sayılmasına gətirmə. Teoremdən belə nəticə çıxır ki, $1$ -dən $n$ -ə qədər olan ədədlər $s f [i]$ qiymətinə görə qruplara bölünür və $(a, b)$ cütü uyğun gəlir ( $a \cdot b$ a \cdot b tam kvadratdır) ancaq və ancaq $a$ və $b$ eyni qrupda yerləşdikdə.

Tutaq ki, $c n t [k]$ $s f [i] = k$ sf[i] = k olan $i (1 \leq i \leq n)$ i~(1 \le i \le n) ədədlərinin sayına bərabərdir. Onu hesablamaq üçün hər bir $i$ üçün $c n t [s f [i]] + +$ cnt[sf[i]]++ əməliyyatını yerinə yetirmək kifayətdir.

Əgər qrupda $m$ ədəd varsa, o zaman bu qrup

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

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

cüt verir. Cavab bütün qruplar üzrə cəmə bərabərdir:

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

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

Ən kiçik sadə bölən. $s f [i]$ -i sürətli hesablamaq üçün $s p f [i]$ massivini daxil edək, bu massiv $i$ ədədinin ən kiçik sadə bölənini göstərir. Məsələn:

$s p f$ massivi Eratosfen ələyinin modifikasiya edilmiş üsulu ilə hesablanır: $p$ sadə ədədi emal edilərkən, $p$ -nin $j$ hər bir kratına (hələ təyin edilməmiş olarsa) $s p f [j] = p$ spf[j] = p qiyməti mənimsədilir.

$s p f$ massivi olduqda, hər bir ədədin kvadratsız hissəsini $s f [i]$ hesablamaq olar. Tutaq ki, $p$ — $i$ ədədinin ən kiçik sadə bölənidir ( $s p f [i] = p$ spf[i] = p). İki hal nəzərdən keçirək:

$p$ $i$ ədədinin ayrılışında ən azı iki dəfə rast gəlinir. Bu o deməkdir ki, $i$ ədədi $p^{2}$ p^2-ə bölünür. İki eyni $p$ sadə vuruğu tam kvadrat əmələ gətirir, buna görə onları kvadratsız hissədən çıxarmaq olar:

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

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

Məsələn:

$s f [12] = s f [3]$ sf[12] = sf[3], çünki $s p f [12] = 2$ spf[12] = 2 və $12$ ədədi $2^{2}$ 2^2-ə bölünür;
$s f [45]$ = $s f [5]$ , çünki $s p f [45] = 3$ spf[45] = 3 və $45$ ədədi $3^{2}$ 3^2-ə bölünür;

$p$ $i$ ədədinin ayrılışında yalnız bir dəfə rast gəlinir. Buna görə $p$ vuruğu kvadratsız hissədə qalmalıdır:

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

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

Məsələn:

$s f [30] = s f [15] \cdot 2$ sf[30] = sf[15] \cdot 2, çünki $s p f [30] = 2$ spf[30] = 2 və $30$ ədədi $2^{2}$ 2^2-ə bölünmür;
$s f [18] = s f [9] \cdot 2$ sf[18] = sf[9] \cdot 2, çünki $s p f [18] = 2$ spf[18] = 2 və $18$ ədədi $2^{2}$ 2^2-ə bölünmür;

Misal

$n = 10$ n = 10 üçün cavabı hesablayaq.

i & vuruqlara ayrılma & kvadratsız hissə

$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$

Ədədləri $s f [i]$ -ə görə $c n t$ massivində qruplaşdıraq.

$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)

Cavab bərabərdir

\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

Alqoritmin realizasiyası

Sabitləri və massivləri elan edək.

#define MAXN 1000000
#define MOD 1000000007
int spf[MAXN + 1];     // ədədin minimal sadə böləni
int sf[MAXN + 1];      // ədədin kvadratsız hissələri
int cnt[MAXN + 1];     // verilmiş sf-ə malik ədədlərin sayı

$n$ giriş qiymətini oxuyuruq.

scanf("%d", \&n);

Eratosfen ələyi üsulunu tətbiq edərək, $s p f$ massivini doldururuq:

$s p f [i]$ $i$ ədədinin minimal sadə bölənini saxlamalıdır

Əvvəlcə hər bir ədədin özünə bölündüyünü fərz edirik. Lakin bu müvəqqətidir.

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

$i$ dəyişənində $2$ -dən $n$ \sqrt{n}-ə qədər ədədləri gəzirik.

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

Əgər $i$ ədədi sadədirsə, $j$ dəyişənində $i^{2}, i^{2} + i, i^{2} + 2 i, ...$ i^2, i^2 + i, i^2 + 2i, ... ədədlərini gəzirik. Bütün bu ədədlərin $i$ sadə böləni vardır (çünki $s p f [i] = i$ spf[i] = i). Əgər $s p f [j] = j$ spf[j] = j olarsa, onda $j$ ədədi üçün minimal sadə böləni yeniləyirik.

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

Hər bir $i$ ədədi üçün onun kvadratsız hissəsini hesablayırıq. Nəticəni $s f [i]$ -ə yazırıq.

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

$p$ dəyişəni $i$ ədədinin ən kiçik sadə bölənini saxlayır.

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

Əgər $i$ ədədi $p^{2}$ p^2-ə bölünürsə, onda $s f [i] = s f [i / p^{2}]$ sf[i] = sf[i / p^2].

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

Əgər $i$ ədədi $p^{2}$ p^2-ə bölünmürsə (lakin $p$ -yə bölünür), onda $s f [i] = s f [i / p] \cdot p$ sf[i] = sf[i / p] \cdot p.

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

Ədədləri onların kvadratsız hissəsinə görə qruplaşdırırıq.

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

Cavabı — axtarılan cütlərin sayını hesablayırıq.

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

Cavabı çap edirik.

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