d × d ≤ n байх d-г шалгаж, хуваагчдыг хосоор нь олоод тоо ба нийлбэрийг нь бодно.

Pre-IntermediateХугацаа: O(√n)Санах ой: O(1)
HackerRank дээр бодох

Эхлээд жижиг бодлого

n = 12. d = 1-ээс эхэлнэ: 1 хуваагч, хос нь 12. d = 2, хос нь 6. d = 3, хос нь 4. d = 4 болоход 4 × 4 = 16 > 12 тул зогсоно.

Хуваагчид: 1, 2, 3, 4, 6, 12. Тоо нь 6, нийлбэр нь 28.

Энгийн аргаас санаа руу

Энгийн арга бол 1-ээс n хүртэлх бүх d-г шалгах: O(n). n = 10¹² бол хэтэрхий удаан.

Хуваагчид хос хосоороо ирдэг: d хуваагч бол n / d бас хуваагч. Хос бүрийн бага нь √n-ээс хэтрэхгүй. Тиймээс зөвхөн d × d ≤ n хүртэл шалгаж, олдсон бүрт хосыг нь давхар нэмнэ.

Нэр томьёо ба тэмдэглэгээ

d
Шалгаж буй бага хуваагч, 1-ээс √n хүртэл.
n / d
d-гийн хос хуваагч, √n-ээс багагүй.
cnt, sum
Хуваагчдын тоо ба нийлбэр.
d
1
2
3
4
5
6
n / d
n = 36cnt = 0sum = 0
хуваагчид
хоосон

36-гийн хуваагчдыг тоолж, нийлбэрийг нь олъё. Хуваагчид хос хосоороо ирдэг: d хуваагч бол n / d бас хуваагч. Тиймээс d × d ≤ 36 байх d-г, өөрөөр хэлбэл 1-ээс 6 хүртэл шалгахад л хангалттай.

Алхам 1 / 17
Хурд
  • Шалгаж буй d
  • Сая нэмсэн
  • Хуваагч биш
  • Хуваагч
  • d × d = n (нэг л удаа)
Слайд 1 / 6

Хуваагчид хосоороо

36-гийн хуваагчид хос хосоороо: 1 × 36, 2 × 18, 3 × 12, 4 × 9, 6 × 6. Хос бүрийн нэг нь √36 = 6-аас бага эсвэл тэнцүү.

divisors.cpp
#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
cin >> n;
long long cnt = 0, sum = 0;
for (int d = 1; d * d <= n; d++) {
if (n % d == 0) {
cnt++, sum += d;
if (d * d != n) {
cnt++, sum += n / d;
}
}
}
cout << cnt << ' ' << sum << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

n хэдэн хуваагчтай, тэдгээрийн нийлбэр хэд болохыг √n алхамд олно. Төгс тоо, хуваагчтай холбоотой бодлогод хэрэглэнэ.

Яаж ажилладаг вэ?

1. d = 1, 2, 3, … гэж d × d ≤ n байх хооронд давтана. 2. n % d = 0 бол d хуваагч: cnt++, sum += d. 3. Түүний хос n / d бас хуваагч. d × d ≠ n бол түүнийг бас нэмнэ. 4. d × d = n бол хос нь d өөрөө тул нэг л удаа тоолно. Оролт: n. Хуваагчдын тоо ба нийлбэрийг хэвлэнэ.

Яагаад зөв, хэр хурдан бэ?

d × d < n байх хуваагч бүр n / d > √n гэсэн өөр хостой тул хос бүрийг нэг удаа олж, хоёуланг нь тоолно. d × d = n үед хос нь өөрөө тул нэг удаа л тоолно. √n-ээс их хуваагч бүр яг нэг бага хуваагчийн хос тул алгасагдахгүй.

Loop √n удаа ажиллана: n = 10¹² бол 10⁶ алхам. Хуваагчдын нийлбэр n-ээс хэд дахин их байж болох тул long long хэрэглэнэ.

Түгээмэл алдаа

  • Квадрат тоон дээр √n-ийг 2 удаа тоолох. 36 дээр 6-г хоёр удаа нэмбэл 10 хуваагчтай, нийлбэр нь 97 гэж буруу гарна.
  • d * d <= n дээр int хэтрэх. n нь 10¹² орчим бол d-г long long болго.
  • d <= sqrt(n) гэж бодит тоогоор шалгах. Бутархайн алдаанаас болж нэг d дутаж болно. Бүхэл тоогоор d * d <= n гэж бич.

Хязгаарын тохиолдол

  • n = 1: d = 1 ба 1 × 1 = 1 тул нэг л удаа тоолно. Хариу: 1 хуваагч, нийлбэр 1.
  • n анхны тоо: зөвхөн d = 1 хуваагч, хариу нь 2 хуваагч, нийлбэр n + 1.
  • n квадрат тоо: хуваагчдын тоо сондгой гарна.

Өөрийгөө шалга

  1. n = 16 бол хуваагчдын тоо, нийлбэр хэд вэ?

    Хариу харах

    5 ба 31. Хуваагчид: 1, 2, 4, 8, 16.

  2. n = 13 бол хариу юу вэ?

    Хариу харах

    2 хуваагч, нийлбэр 14.

  3. n = 10⁹ бол хамгийн ихдээ хэдэн d шалгах вэ?

    Хариу харах

    31 622. 31 622² ≤ 10⁹ < 31 623².

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.n = 28-ын хуваагчдыг ол. Өөрийг нь оруулалгүй хуваагчдын нийлбэр 28-тай тэнцүү юу?

    Hint харах

    d = 1, 2, 4 гурав л хуваагч олдоно.

    Хариу ба тайлбар

    1, 2, 4, 7, 14, 28. Нийлбэр 56 = 2 × 28 тул өөрийг нь хасвал 28. Ийм тоог төгс тоо гэнэ.

  2. 2.Хуваагчдыг өсөх дарааллаар хэвлэдэг болго.

    Hint харах

    Бага хуваагчид аль хэдийн өсөх дараалалтай. Хосууд нь буурах дараалалтай.

    Хариу ба тайлбар

    Бага хуваагчдыг нэг vector-д, хосуудыг нөгөө vector-д хийнэ. Эхнийхийг шууд, хоёрдахийг урвуу дарааллаар хэвлэнэ.

  3. 3.1-ээс n хүртэлх бүх тооны хуваагчдын тоог нэг дор ол.

    Hint харах

    Тоо бүрийг шалгахын оронд d бүрийг түүний үржвэрүүдэд нэмж тараа.

    Хариу ба тайлбар

    for d = 1..n: for (j = d; j <= n; j += d) cnt[j]++; Нийт n/1 + n/2 + … ≈ n ln n алхам, O(n log n).

Жишээ

Оролт

36

Гаралт

9 91

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.