切換
舊版
前往
大廳
主題

ZeroJudge - d444: 排容原理 解題心得

Not In My Back Yard | 2018-08-11 22:45:29 | 巴幣 0 | 人氣 229

題目連結:

題目大意:
給定N、M,和以及接下來的M個數字(1 < N、M個數字總乘積 < 2147483647,M ≦ 15)。求在N中,不是那M個數字任意一個的倍數之數量。

解題思維:
單純的排容原理以及最大公因數的演算法,因為M個數字彼此不一定互質。

排容原理說明:
對於 N = 25,M = 3,3 個數字為 2 、 3 、 5。對於那 3 個數字可以先各自扣掉自己的倍數數量,得 0;因為同時多扣了 2 和 3 的倍數、 2 和 5 的倍數,以及 3 、 5 的倍數,將其加回來,得 7 ;最後可能多加了 2 和 3 和 5 的倍數,所以再扣掉,得 7 。

而 7 正是我們所以的答案。

其他的例子也是以此類推,但是要小心 M 個數字間不一定互質。



此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大們可以提出來討論。

創作回應

相關創作

更多創作