傳送門 我們可以先考慮下三角矩陣，之后答案*2（上三角矩陣）+3右下角三個(gè)特殊點(diǎn)。 顯然當(dāng)坐標(biāo)i，j(i,j)!=1滿足gcd(i,j)=1時(shí)可以看得見。 所以我們用線性篩求歐拉函數(shù)，答案就是sigma(phi(i))*2+3(2<=i<=n).
#include<iostream>#include<cstdio>using namespace std;int n,ans,s,p;int main(){ scanf("%d",&n); ans=0; for (int i=2;i<n;i++){ s=i,p=i; for (int j=2;j*j<=p;j++) if (p%j==0){ s=s*(j-1)/j; while (p%j==0) p/=j; } if (p!=1) s=s*(p-1)/p; ans+=s; }新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
