Rumah > Artikel > pembangunan bahagian belakang > 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.
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.
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.
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.
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.
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
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; }
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 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
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
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; }
For the interval [1, 10] maximum occurring divisor = 2
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.
Proses maxDivisors (a, b)
jika a == b
ans = a
Lain-lain
man = 2
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; }
For the interval [1, 10] maximum occurring divisor = 2
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!