Exactly what I was looking for. Thank you so much, Anant!
Programming Languages
A community where the advantages and disadvantages of different programming languages is discussed. Moreover, it should also include some of the best tutorials across the web for learning them.
Hey, Try thinking over the program below for sometime.
//LCM very quickly becomes larger than no of leaves so check if bound == 0 #include <iostream> #define ui unsigned int using namespace std; ui leaves,caterpillars; ui caterpillar[21]; //HCF(a,b) = HCF(b,a%b) //Euclidean Algorithm ui HCF(ui a, ui b) { if(b == 0) return a; else return HCF(b, a % b); }ui recur(ui start, ui cumulative, ui bound) { if(bound == 0) return bound; ui g = caterpillar[start]/HCF(cumulative, caterpillar[start]); ui result = bound/g; for(ui j = start + 1; j < caterpillars; j++) result -= recur(j, cumulative*g, bound/g); return result; } int main() { cin >> leaves >> caterpillars; for(ui i = 0; i < caterpillars; i++) cin >> caterpillar[i]; ui undamaged = leaves - 1; for(ui i = 0; i < caterpillars; i++) undamaged -= recur(i, 1, leaves - 1); cout << undamaged; return 0;
Damaged leaves = Sum of unique leaves damaged by each and every caterpillar. Remember that every iteration of i subtracts only the unique multiples of caterpillar[i]. Every iteration of 'j' removes the non-unique multiples from all multiples of caterpillar[i]. (leaves-1)/length gives number of leaves damaged by caterpillar of certain length. We divide (leaves-1) by LCM of a set of numbers to remove non-unique multiples of caterpillar[i]. bound check is done to avoid further calculation when LCM already exceeds number of leaves. Hope these hints are enough to understand the code above.