2018年2月7日

[程式] 排容原理實作 (inclusion-exclusion principle implementation)

由於先前這一篇會用到排容原理,因此就花了點時間研究排容原理要怎麼實作比較好。不過這玩意兒因為只是個原則,實作方法會根據要處理的問題有些許差別,這邊的實作針對的是以下的問題:

給定兩個正整數 $n$ 跟 $x$,要找出有多少正整數 $y$ 使得 $y < n \ \& \ gcd(y, x) = 1$,其中 $gcd$ 代表最大公因數


詳細的說明有放在實作中了,這邊就不多做解釋,實作如下:

沒有留言:

張貼留言