本文共 1668 字,大约阅读时间需要 5 分钟。
问题 : 机智的手机商(容斥)
题目描述
你是一个喜欢编程的手机经销商,一次你得到了一个边长为n的正方体箱子,里面装满了长,宽,高为a,b,c的华为手机盒,手机盒均朝同一方向摆放。这时,一束阳光正好照过正方体箱子的对角线,你想知道,这一束阳光穿过了多少手机盒。
(n<=100000,a,b,c均为n的约数)
输入
输入4个正整数,分别表示n,a,b,c
输出
输出光束穿过手机盒的数量
解析
这是三维模型:
这个十分难想,但是我们知道维度与维度之间有很多相似性,所以我们可以先考虑二维模型。
从上面我们可以发现,这束红光只能从两条边穿过一个矩形,上面和左边,那么我们就可以分开看。
从上面一眼就能看出,每一列的矩形都有且仅有一个矩形,阳光从其左边穿过,这是肯定的。每一行也一样,都有一个矩形是从上面穿过阳光的。那么左边穿过的就有n / a 个,上面的就有 n / b 个,总共有 n/a + n/b 个矩形。
但是,我们发现还有一些是从顶点穿过的(最左上角),这个数目非常可观,就是n / lcm(a,b)(最小公倍数),这些要排除。
所以总的方案数就是 n / a + n / b - n / lcm(a,b) 。
三维的就可以推出来了。
三维的每一个小长方体都有三种情况会被对角线穿过,就是上图所指的地方,上面,还有两个侧面(分别是长和宽,长和高,宽和高组成的三个面)方法数总和就是 n / a + n / b + n / c。而其中任意两种情况都有重合的可能,重合的也有三种情况:
根据上面推导的,三种情况都很可观,总数是 n / lcm(a,b) + n / lcm(b,c) + n / lcm(a,c) 。
减去这些后,我们会发现还有情况被减没了。
这三种情况也可能重合,需要加上。重合过后就是恰好穿过顶点:
那么就是他的位置恰好是a,b,c三者共同的倍数,总数就是 n / lcm(a,b,c) 。
最后的答案就是 n / a + n / b + n / c - n / lcm(a,b) - n / lcm(b,c) - n / lcm(a,c) + n / lcm(a,b,c)。
其中的 lcm(a,b,c) = lcm(lcm(a,b),c), lcm(a,b) = a * b / gcd(a,b),
gcd(a,b) = gcd(b,a mod b),gcd(x,0) = x;
代码:
#include#include #include #include using namespace std;int read() { int f = 1,x = 0;char s = getchar(); while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();} while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();} return x * f;}int n,m,i,j,k,s,o,a,b,c;int gcd(int a,int b) { return b == 0? a : gcd(b,a % b);}int lcm(int a,int b) { return a * b / gcd(a,b);}int lcm(int a,int b,int c) { return lcm(a,lcm(b,c));}int main() { n = read();a = read();b = read();c = read(); printf("%d",n / a + n / b + n / c - n / lcm(a,b) - n / lcm(b,c) - n/lcm(a,c) + n/lcm(a,b,c)); return 0;}
转载地址:https://blog.csdn.net/weixin_43960414/article/details/88739130 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!