题意很简单，求sum(gcd(i,n))   1<=i<=n;

这题看到后第一反应并没有里用积性函数的性质，不过也可以做，欣慰的是我反应还是比较快的

设f(n)=gcd(1,n)+gcd(2,n)+....+gcd(n-1,n) + gcd(n,n)，

用g(n,i)表示满足 gcd(x,n)=i的 x的个数 （x小于n），则 f(n)=sum{i*g(n,i)};

同时又利用 扩展欧几里德的性质  gcd(x,n)=i  的充要条件是 gcd(x/i,n/i)==1，所以 满足 x/i的解有 phi(n/i)个，说明  g(n,i)=phi(n/i),

这样的方法进行推论 貌似以前遇到过，记不清楚了，反正推的还挺快的，一开始直接线性phi_table预处理phi数组，结果RE了，后来发现题目的n比较大，刚好卡到int，所以只好先求出一定范围内的素数，用euler函数进行求值，

在累加求f(n)的时候有个技巧，只需扫到sqrt(n)即可，一看就明白了，这个过了再想想积性函数的方法

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>
#include<cctype>

#define ll long long

#define LL __int64

#define eps 1e-8

#define inf 0xfffffff

//const ll INF = 1ll<<61;

using namespace std;

//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;


const int N = 1000010;

ll prime[N];

bool isprime[N];

ll cnt;
void init()//这段求出了N内的所有素数
{
	ll i,j;
	for(i=2;i<=N;i++) {
		if(!isprime[i])
			prime[cnt++]=i;
		for(j=0;j<cnt && i*prime[j]<=N;j++) {
			isprime[i*prime[j]] = true;
		}
	} 
	cnt--;
	isprime[1] = true;
}

ll euler(ll n)//这里利用上面求出来的 素数来进行求解就会快很多，
{
	ll i;
	ll tempn = n;
	ll ans = n;
	for(i=0;i<=cnt && prime[i]*prime[i]<=n;i++) {
		if(n%prime[i] == 0) {
			ans = ans / prime[i] * (prime[i] - 1);
			while(tempn%prime[i] == 0)
				tempn /= prime[i];
		}
	}
	if(tempn > 1)
		ans = ans / tempn * (tempn - 1);
	return ans;
}

LL n;

int main() {
	init();
	while(scanf("%I64d",&n) == 1) {
		LL ans = 0;
		for(LL i=1;i<=sqrt(n * 1.0);i++) {
			if(i * i == n) {
				ans += i * euler(n/i);
				continue;
			}
			if(n%i == 0) {
				ans += i * euler(n/i);
				LL tmp = n/i;
				ans += tmp * euler(i);
			}
		}
		printf("%I64d\n",ans);
	}
	return 0;
}

常见的积性函数：

φ(n) －欧拉函数，计算与n互质的正整数之数目　

μ(n) －莫比乌斯函数，关于非平方数的质因子数目

gcd(n,k) －最大公因子，当k固定的情况　

这个时候令g(k) =gcd(n,k),1<=n<=k,那么g(k*x) = g(k) * g(x),也就是积性函数 ，这个时候一般和是不会改变什么情况的，所以我先大胆猜测了一般，题目要求的不就是f(n) = sum(gcd(i,n))，也就是积性函数 相加 得到的一个新函数是否是积性函数呢，百度不好搜到，我没那么强大去证明，所以举了几个例子，发现没错，然后又专门写了个程序算了一下比较大的数的情况，然后又用计算器按了一下，发现没错，然后翻看了一些人题解的分析，有人说了这么一句话：由具体数学上的结论，积性函数的和也是积性的。都扯到什么具体数学了，反正我是没学过这么高端的数学，只好死记好这个结论了，那么接下来处理积性函数的部分就跟HDU2879差不多了

百度百科搜积性函数也是有图片说明的：

若n = p1^a1 * p2^a2....省略号后我都懂得~

那么f(n) = f(p1^a1) * f(p2^a2) ...呵呵

所以求以下f(pi^ai)就可以咯，怎么算呢，这下可以利用这道题的我的上一种方法：

上个方法说到：用g(n,i)表示满足 gcd(x,n)=i的 x的个数 （x小于n），这句话中的x其实是n的一个约数，所以我们这个时候令x为n的一个约数，这时候gcd(i,n) = x的个数就是phi(n/x),跟上一个方法类似的证明

然后就可以用筛法求了，

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>
#include<cctype>

#define ll long long

#define LL __int64

#define eps 1e-8

#define inf 0xfffffff

//const ll INF = 1ll<<61;

using namespace std;

//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;


int main () {
	LL n;
	while(scanf("%I64d",&n) == 1) {
		LL ans = n;
		LL tmp = sqrt(n * 1.0);
		for(LL i=2;i<=tmp;i++) {
			if(n%i == 0) {
				LL cnt = LL(0);
				while(n%i == 0) {
					n /= i;//筛法
					cnt++;
				}
				ans += ans * cnt * (i - 1)/i;
			}
		}
		if(n != 1)
			ans += ans * (n - 1)/n;
		printf("%I64d\n",ans);
	}
	return 0;
}