Every k-th, l-th, m-th, n-th dragon will be damaged,
How many dragons suffered damage , if the princess counted a total of D dragons?
1. Straightforward way
The number of dragons D can be quite small, so the problem can be solved in a straightforward way,
by iterating over dragons 1 through D and checking each dragon individually.
int f(vector<int> &nums ,int d){ //k平底锅脸、l门尾巴、m高跟鞋爪子、n叫妈妈
int res = d;
for(int i=1;i<=d;i++){//判断每一头龙
bool flag = false;
for(int j=0;j<nums.size();j++){
if(i%nums[j]==0){
flag = true;
break;
}
}
if(!flag) res--;
}
return res;
}
2. Inclusion-exclusion principle
Calculate LCM of the corresponding sets of numbers
Finally, the number of dragons that get damaged equals N1 - N2 + N3 - N4
int gcd(int a, int b) {
return b?gcd(b, a % b):a;
}
int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}
int f(vector<int> &nums ,int d){ //k平底锅脸、l门尾巴、m高跟鞋爪子、n叫妈妈
int res = 0;
int n = nums.size();
int flag;
for (int mask = 1; mask < (1 << n); mask++) {//遍历所有子集
int cur_lcm = 1;
for(int i=0;i<n;i++) //求当前集合最小公倍数
if( (mask>> i) & 1 == 1)
cur_lcm = lcm(cur_lcm,nums[i]);
flag = __builtin_popcount(mask)%2==1?1:-1;
res+= flag*(d/cur_lcm);
}
return res;
}