題目描述

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

輸入

一個整數(shù)，為N。

輸出

一個整數(shù)，為所求的答案。

樣例輸入

6

樣例輸出

15

---

題解

歐拉函數(shù)

易得知滿足gcd(n,x)==i的小于等于n的x的個數(shù)為phi(n/i)，

并且歐拉函數(shù)可以在O(√n)的時間內(nèi)快速求出。。

于是可以先求出所有n的因子，再用歐拉函數(shù)得出答案。

由于因子是成對出現(xiàn)的，所以因子并不需要枚舉到n，只需枚舉到√n。如果i是n的因子，那么n/i也是n的因子，注意此時i*i==n不能算進答案內(nèi)。

#include <cstdio> typedef long long ll; ll phi(ll x) {ll ans = x , t = x , i;for(i = 2 ; i * i <= x ; i ++ ){if(t % i == 0) ans = ans * (i - 1) / i;while(t % i == 0) t /= i;}if(t > 1) ans = ans * (t - 1) / t;return ans; } int main() {ll n , i , ans = 0;scanf("%lld" , &n);for(i = 1 ; i * i <= n ; i ++ ){if(n % i == 0){ans += i * phi(n / i);if(i * i < n) ans += (n / i) * phi(i);}}printf("%lld\n" , ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/GXZlegend/p/6633646.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。