正題

---

大意

給出一個nn，求1～n1～n里面和nn互質的數的和。

---

解題思路

φ(i)φ(i)表示的就是1～i1～i里面和ii互質的個數。然后數字和就是φ(i)?i/2φ(i)?i/2。

---

代碼

#include<cstdio> #include<cmath> #include<algorithm> #define ll long long using namespace std; ll a,ans,n; int main() {scanf("%lld",&a);n=a;ans=a;for (ll i=2;i<=sqrt(a);i++)if (a%i==0){ans=ans/i*(i-1);//計算while(a%i==0) a/=i;//取出質數}if (a>1) ans=ans/a*(a-1);//處理a=2的特判printf("%lld",n*ans/2); }

總結

以上是生活随笔為你收集整理的jzoj1164-求和【欧拉函数,数论】(筛欧拉函数模板)的全部內容，希望文章能夠幫你解決所遇到的問題。

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