题目背景

SDOi2012

题目描述

Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。

输入输出格式

输入格式：

一个整数，为N。

输出格式：

一个整数，为所求的答案。

输入输出样例

输入样例#1：

6

输出样例#1：

15

说明

对于60%的数据，0

#include<stdio.h>

#include<math.h>

typedef long long ll;

ll euler(ll x)//欧拉函数

{

    ll ans=x,tp=sqrt(x);

    for(ll i=2;i<=tp;++i)

        if(x%i==0)

        {

            ans=ans-ans/i;

            while(x%i==0)  x/=i;

        }

    if(x>1)  ans=ans-ans/x;

    return ans;

}

int main()

{

    ll n;

    scanf("%lld",&n);

    ll ans=0,tp=sqrt(n);

    for(ll i=1;i<=tp;++i)

      if(n%i==0)  ans+=i*euler(n/i)+n/i*euler(i);

    if(tp*tp==n) ans-=tp*euler(tp);

        printf("%lld\n",ans);

    return 0;

}