邁向王者的旅途
2018年2月7日
[程式] 排容原理實作 (inclusion-exclusion principle implementation)
由於先前
這一篇
會用到排容原理,因此就花了點時間研究排容原理要怎麼實作比較好。不過這玩意兒因為只是個原則,實作方法會根據要處理的問題有些許差別,這邊的實作針對的是以下的問題:
給定兩個正整數 $n$ 跟 $x$,要找出有多少正整數 $y$ 使得 $y < n \ \& \ gcd(y, x) = 1$,其中 $gcd$ 代表最大公因數
詳細的說明有放在實作中了,這邊就不多做解釋,實作如下:
沒有留言:
張貼留言
較新的文章
較舊的文章
首頁
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言