pembahagi sepunya terbesar dalam selang

Biar x dan y ialah dua nombor. Dalam kes ini, x dikatakan pembahagi y jika y mengembalikan baki sifar apabila dibahagikan dengan x. Pembahagi terbesar yang berlaku dalam selang adalah pembahagi bilangan terbesar unsur dalam selang.

Pernyataan Masalah

Diberi selang [a, b]. Cari pembahagi terbesar yang berlaku dalam julat yang mengandungi a dan b (selain daripada "1"). Mengembalikan 1 jika semua pembahagi berlaku bilangan kali yang sama.

Contoh 1

Input [2, 5]

Output 2

Penjelasan - Pembahagi 2 = {1, 2}, pembahagi 3 = {1, 3}, pembahagi 4 = {1, 2, 4}, pembahagi 5 = {1, 5} . 2 adalah pembahagi yang paling kerap.

Contoh 2

Input [2, 5]

Output 2

Penjelasan - Pembahagi 2 = {1, 2}, pembahagi 3 = {1, 3}, pembahagi 4 = {1, 2, 4}, pembahagi 5 = {1, 5} . 2 adalah pembahagi yang paling kerap.

Kaedah 1: Brute force cracking

Cara brute force untuk menyelesaikan masalah ini adalah dengan mencari semua pembahagi semua nombor dalam selang dan menyimpannya dalam peta bersama-sama dengan bilangan kejadian.

Algoritma

Pembahagi proses (bilangan)

• Untuk i = 1 hingga n1/2+1

• Jika num%i == 0

• Jika nombor/i == i

• Jika saya tiada dalam peta, masukkan (i, 1)

• Jika tidak peta[i]++

• Lain-lain

• Jika saya tiada dalam peta, masukkan (i, 1)

• Jika tidak peta[i]++

• Jika nombor/i tiada dalam peta, masukkan (nombor/i, 1)

• Peta lain[num/i]++

Proses maxDivisors (a, b)

• untuk n = a hingga b

• Pembahagi (n)

• map.erase(1)

• divisor = 1, count = int_min

• Untuk setiap elemen dalam peta

• jika ia.nilai > kira

• kira = it.value

• Pembahagi = it.key

Contoh: Pelaksanaan C++

Dalam atur cara di bawah, kita mencari pembahagi setiap nombor dalam fungsi pembahagi() dan mencari pembahagi berlaku terbesar dalam fungsi maxdivisor().

#include <bits/stdc++.h>
using namespace std;

// map storing occurrence of each divisor
unordered_map<int, int> occ;

// function to find all the divisors of a number and store it in map
void divisors(int num){
   for (int i = 1; i <= (sqrt(num) + 1); i++)    {
   
      // checking if i is divisor of num
      if (num % i == 0)        {
      
         // checking if num has identical divisors i.e. if i*i == num
         // if identical divisors then save only one
         if (num / i == i) {
            if (occ.find(i) == occ.end()) {
               occ.insert(make_pair(i, 1));
            }
            else{
               occ[i]++;
            }
         }
         else{
         
            // saving divisor i
            if (occ.find(i) == occ.end()) {
               occ.insert(make_pair(i, 1));
            }
            else{
               occ[i]++;
            }
            
            // saving the divisor of num corresponding to i
            if (occ.find(num / i) == occ.end()) {
               occ.insert(make_pair(num / i, 1));
            }
            else{
               occ[num / i]++;
            }
         }
      }
   }
}

// function to find maximum occurring divisor in an interval
int maxDivisor(int a, int b){
   for (int n = a; n <= b; n++){
      divisors(n);
   }
   
   // deleting all occurrences of 1 as 1 is not to be returned until the interval is [1,1]
   occ.erase(1);
   
   // divisor set as 1 for edge case scenario when interval is [1,1]
   int div = 1, cnt = INT_MIN;
   for (auto it = occ.begin(); it != occ.end(); it++) {
      if (it->second > cnt) {
         cnt = it->second;
         div = it->first;
      }
   }
   return div;
}
int main(){
   int a = 4, b = 7;
   cout << "For the interval [" << a << ", " << b << "] maximum occurring divisor = ";
   cout << maxDivisor(a, b);
   return 0;
}

Output

For the interval [4, 7] maximum occurring divisor = 2

Kerumitan masa - O(n3/2), kerana untuk setiap nombor dalam selang, untuk mencari pembahagi, gelung kerumitan O(n1/2) dilakukan.

Kerumitan ruang - O(n), ruang peta.

Kaedah 2

Kaedah di atas boleh dioptimumkan lagi dengan mengurangkan masa untuk mengisi peta dengan setiap kejadian pembahagi. Daripada mencari pembahagi setiap nombor, anda boleh mempelajari kejadian setiap pembahagi dalam selang dengan mengira sempadan bawah dan atas selang.

Mari kita ambil selang [2, 5] sebagai contoh.

Set pembahagi yang mungkin adalah dari 1 hingga 5. Oleh itu, 1 = 5/1 - 2/1 +1 = 4 berlaku. Nampaknya 2 = 5/2 - 2/2 + 1 = 2. Nampaknya 3 = 5/3 - 2/3 = 1. Nampaknya 4 = 5/4 - 2/4 = 1. Nampaknya 5 = 5/5 - 2/5 = 1.

Di atas boleh diformalkan sebagai,

Jika sempadan bawah% pembahagi == 0 maka occ = sempadan atas/pembahagi - sempadan bawah/pembahagi + 1

Occ lain = sempadan atas/pembahagi - sempadan bawah/pembahagi

Algoritma

Proses maxDivisor (a, b)

• untuk i = 2 hingga b

• Jika a%i == 0

• Bilangan kali = b/i - a/i +1

• Lain-lain

• Bilangan kali = b/i - a/i

• map.insert(i, times)

• divisor = 1, count = int_min

• Untuk setiap elemen dalam peta

• jika ia.nilai > kira

• kira = it.value

• Pembahagi = it.key

Contoh: Pelaksanaan C++

Dalam atur cara di bawah, bukannya mencari pembahagi nombor dalam susunan terbalik, kami mencari untuk setiap pembahagi berapa banyak gandaan yang ada dalam selang itu.

#include <bits/stdc++.h>
using namespace std;

// function to find maximum occurring divisor in an interval
int maxDivisor(int a, int b){

   // map used to store occurrences of divisors
   unordered_map<int, int> occ;
   for (int i = 2; i <= b; i++){
      int times;
      if (a % i == 0){
         times = (b / i) - (a / i) + 1;
      }
      else{
         times = (b / i) - (a / i);
      }
      occ.insert(make_pair(i, times));
   }

   // divisor set as 1 for edge case scenario when interval is [1,1]
   int div = 1, cnt = INT_MIN;
   for (auto it = occ.begin(); it != occ.end(); it++){
      if (it->second > cnt){
         cnt = it->second;
         div = it->first;
      }
   }
   return div;
}
int main(){
   int a = 1, b = 10;
   cout << "For the interval [" << a << ", " << b << "] maximum occurring divisor = ";
   cout << maxDivisor(a, b);
   return 0;
}

Output

For the interval [1, 10] maximum occurring divisor = 2

Kaedah 3

Penyelesaian yang sangat mudah untuk masalah ini ditunjukkan di bawah,

Dalam sebarang selang saiz > 1, separuh nombor (setiap nombor genap) akan mempunyai 2 sebagai pembahaginya.

Jadi ia boleh digunakan seperti berikut.

Algoritma

Proses maxDivisors (a, b)

• jika a == b

• ans = a

• Lain-lain

• man = 2

Contoh: Pelaksanaan C++

Dalam program di bawah, kami melaksanakan pemerhatian bahawa setiap nombor genap mempunyai 2 sebagai pembahagi.

#include <bits/stdc++.h>
using namespace std;

// function to find the maximum occurring divisor in an interval
int maxDivisor(int a, int b){
   if (a == b){
      return a;
   } else {
      return 2;
   }
}
int main(){
   int a = 1, b = 10;
   cout << "For the interval [" << a << ", " << b << "] maximum occurring divisor = ";
   cout << maxDivisor(a, b);
   return 0;
}

Output

For the interval [1, 10] maximum occurring divisor = 2

Kesimpulan

Ringkasnya, untuk mencari pembahagi kejadian terbesar dalam selang, kita boleh menggunakan kaedah di atas, julat masa adalah dari O(n3/2) hingga O(1), dan julat ruang adalah dari O(n) kepada O( 1).

Atas ialah kandungan terperinci pembahagi sepunya terbesar dalam selang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!