Time Limit:?3 Sec??Memory Limit:?128 MB
Submit:?3874??Solved:?2469
[Submit][Status][Discuss]

Description

Longge的數學成績非常好，并且他非常樂于挑戰高難度的數學問題?，F在問題來了：給定一個整數N，你需要求出∑gcd(i, N)(1<=i <=N)。

Input

一個整數，為N。

Output

一個整數，為所求的答案。

Sample Input

6

Sample Output

15

HINT

?

【數據范圍】

對于60%的數據，0<N<=2^16。

對于100%的數據，0<N<=2^32。

題目中要求出∑gcd(i,N)(1<=i<=N)。

枚舉n的約數k，令s(k)為滿足gcd(m,n)=k,(1<=m<=n)m的個數，則ans=sigma(k*s(k)) (k為n的約數）

因為gcd(m,n)=k,所以gcd(m/k,n/k)=1,于是s(k)=euler(n/k)

phi可以在根號的時間內求出

?

歐拉函數的定義:

??? 在數論中，對于正整數N,少于或等于N ([1,N]),且與N互質的正整數(包括1)的個數，記作φ(n)。

? ? ?φ函數的值：

??? φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))…..(1-1/p(n)) 其中p(1),p(2)…p(n)為x

的所有質因數;x是正整數; φ(1)=1(唯一和1互質的數，且小于等于1)。注意：每種質因數只有一個。

???? 例如:

???????? φ(10)=10×(1-1/2)×(1-1/5)=4;

???????? 1 3 7 9

???????? φ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8;

???????? φ(49)=49×(1-1/7)=42;

?

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll n,ans;ll phi(ll n){ll ret = n,a = n;for (int i = 2;i <= sqrt(n);++i){if (a % i) continue;ret -= ret/i;while(a % i == 0) a /= i;}if (a > 1) ret -= ret/a;return ret; }int main(){scanf("%lld",&n);ans = 0;for (int i = 1;i <= sqrt(n);++i){if (n%i) continue;ans += i*phi(n/i);if (i*i < n) ans += n/i*phi(i);}printf("%lld\n",ans);return 0; }

?

轉載于:https://www.cnblogs.com/mizersy/p/9739823.html

總結

以上是生活随笔為你收集整理的BZOJ2705 [SDOI2012]Longge的问题 欧拉函数的全部內容，希望文章能夠幫你解決所遇到的問題。

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