A. [2021.1.29多校省選模擬11]最大公約數

這是一個杜教篩的經典題目，最后我們只需要篩一下$1?x\mu (x)$這個函數的前綴和即可，然后看到有$1$這個函數，我們下意識應該想到的就是$\mu$，然后又有$x\mu (x)$所以我們配一個$id$就可以將其抵消為n，最后恰好化簡后為單位函數。

同樣還有一種方法更為簡潔，直接配一個$id$就足夠了，因為$1$和$\mu$可以直接抵消，這樣的結果同樣也是單位函數。

然后這道題我最終只有64分，只是因為我取模出現問題，由于輸入的值高達$1e10$所以有時候計算會有超過$mod$范圍的數，這時候必須再一次$mod$一下。

總結

以上是生活随笔為你收集整理的A. [2021.1.29多校省选模拟11]最大公约数（杜教筛/数论）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。