can anyone resolve better than O(N*N)↵
↵
/predownloaded/9b/e2/9be282ab5ad24ffbfa25b13501f2155c26b50b48.png↵
↵
/predownloaded/3b/ec/3bec38e86fa9432dfa375da46514039cc392d42f.pngProblem Breakdown↵
1. Find LCM for Each Pair:↵
* For each unique pair (a[i], a[j]) in the array a, compute the Least Common Multiple (LCM).↵
* The pairs include (a[i], a[i]) for each single number, as well as every combination of distinct numbers (a[i], a[j]) where i ≠ j.↵
2. Calculate Minimum Multiplier:↵
* For each pair (a[i], a[j]), find the smallest integer mmm such that: LCM(a[i],a[j])×m≥k\text{LCM}(a[i], a[j]) \times m \geq kLCM(a[i],a[j])×m≥k↵
* This product should also be a multiple of kkk.↵
3. Calculate the Cost:↵
* For each pair, compute the cost of the smallest multiplier mmm, which is simply the value of mmm.↵
* Sum up the costs for all pairs to get the total answer.↵
eg: [4,5,6] k=12 ans=>3+12+2+2*(3+2+1)=29, give a complexity less than O(N2) less than 108 as n<=10**5↵
↵
as lcm of(4,4)->4*3=12(multiple of k) (5,5)->5*12=60(mutplit of k) similarly, (6,5)->30*2=60(multiple of k) and (5,6)=2 same answer↵
↵
(4,5)=(5,4)=3 that's why foe different pairs we multiple by 2 for answer
/predownloaded/9b/e2/9be282ab5ad24ffbfa25b13501f2155c26b50b48.png↵
↵
/predownloaded/3b/ec/3bec38e86fa9432dfa375da46514039cc392d42f.png
1. Find LCM for Each Pair:↵
* For each unique pair (a[i], a[j]) in the array a, compute the Least Common Multiple (LCM).↵
* The pairs include (a[i], a[i]) for each single number, as well as every combination of distinct numbers (a[i], a[j]) where i ≠ j.↵
2. Calculate Minimum Multiplier:↵
* For each pair (a[i], a[j]), find the smallest integer mmm such that: LCM(a[i],a[j])×m≥k\text{LCM}(a[i], a[j]) \times m \geq kLCM(a[i],a[j])×m≥k↵
* This product should also be a multiple of kkk.↵
3. Calculate the Cost:↵
* For each pair, compute the cost of the smallest multiplier mmm, which is simply the value of mmm.↵
* Sum up the costs for all pairs to get the total answer.↵
eg: [4,5,6] k=12 ans=>3+12+2+2*(3+2+1)=29, give a complexity less than O(N2) less than 108 as n<=10**5↵
↵
as lcm of(4,4)->4*3=12(multiple of k) (5,5)->5*12=60(mutplit of k) similarly, (6,5)->30*2=60(multiple of k) and (5,6)=2 same answer↵
↵
(4,5)=(5,4)=3 that's why foe different pairs we multiple by 2 for answer
