首页 > 代码库 > POJ2480 Longge's problem 欧拉函数的应用 && 积性函数

POJ2480 Longge's problem 欧拉函数的应用 && 积性函数

题意很简单,求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;
}