即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

51nod-1040 最大公约数之和

编程语言 Snow_Me 17℃ 0评论

解题思路:

这题感觉dalao们会说这题是个水题….虽然这题确实挺简单的…

思路很好想,求最大公约数之和嘛,对于n,从1-n与n之间的最大公约数,必然不可能有n个,也就是必然出现再n的因子中,那么其实可以求sum(a * b),a表示n的因子,b表示最大公约数为a的个数。

那更进一步,gcd(n, m) = k,那么必然会有gcd(n / k, m / k) = 1,那么就可以根据这个,得到最后的结果:

ans = sigma(ki * euler(ki))其中p是n的因子数,sigma表示类和




代码:

#include 
#include 
using namespace std;

int eular( int n ) {
 int ans = n;
 for (int i = 2; i * i <= n; ++i) {
  if (n % i == 0) {
   ans -= ans / i;
   while (n % i == 0) n /= i;
  }
 }
 if (n > 1) ans -= ans / n;
 return ans;
}
int main() {
 int n;
 long long ans;
 while (cin >> n) {
  if (n == 1) cout << "1" << endl;
  else {
   ans = eular(n);
   for (int i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
     ans += i * eular(n / i);
     if ( i * i != n ) ans += n / i * eular(i);
    }
   }
   cout << ans + n << endl;
  }
 }
 return 0;
}





转载请注明:CodingBlog » 51nod-1040 最大公约数之和

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情