題目連結:
題目大意:
給定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 個數字間不一定互質。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大們可以提出來討論。