1
11
2016
1

POJ 2478 Farey Sequence

http://poj.org/problem?id=2478

上次听叶队说欧拉函数前缀和有O(n2/3)的求法,看到这道题就去写了一下。

我们考虑S(n)表示有多少对(x,y)满足gcd(x,y)=1且x,y<=n,那么我们要求的1-n的欧拉函数和即为(S(n)-1)/2,因为gcd(1,1)=1所以需要+1

那么有一个显然的结论,\(\sum_{k=1}^{n}S(n/k)\),其实也很好解释,就是gcd(x,y)的值一定是1-n,那么S(n/i)即为满足gcd(x,y)=i,且x,y<=n的(x,y)对数,那么我们就可以递归求解了。

因为n/i中有很多是相同的,这个有经典的O(sqrt(n))解法,这里不再赘述。

然后为了节约时间,我们应当欧拉筛法预处理出一部分S(i)(1<=i<=m)的答案并对S(n)进行记忆化,以便于计算。通过记忆化搜索,所以时间复杂度可以达到F(n)=\(\sum_{k=1}^{n/m}\sqrt{n/k}\)。

那么总时间复杂度即为m+\(\sum_{k=1}^{n/m}\sqrt{n/k}\),从这里可以看出显然当m取一个int(n/k)+1的值时时间较优。我们假

设m取int(n/k)+1比int(n/(k+1))+1优,那么可得k0.5>n/k-n/(k+1),即k1.5(k+1)>n,可以近似得到k2.5>n,也就是当k=n0.4答案最优,即m取n0.6时答案最优(叶队说是n2/3,不明),时间复杂度为O(n0.6+\(\sum_{k=1}^{{n}^{0.4}}\sqrt{k}\))(然而这个东西显然小于n0.6反正能过10^9)空间复杂度O(m)=O(n0.6)

下面是代码

 

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define eps 1e-6
using namespace std;
int a[10005],phi[10005],vis[10005],prime[1005];
long long an[1005];
int cnt,n,size,N;
void Pre(int n){
	int cnt=0;
	memset(vis,0,sizeof(vis));
	for(int i=2;i<n;i++){
		if(!vis[i]){
			prime[cnt++]=i;
			phi[i]=i-1;
		}
		for(int j=0;j<cnt&&i*prime[j]<n;j++){
			long long k=i*prime[j];
			vis[k]=1;
			if(i%prime[j]==0){
				phi[k]=phi[i]*prime[j];
				break;
			}
			else
			phi[k]=phi[i]*(prime[j]-1);
		}
	}
}
long long work(int N){
	if(N<=10000)return a[N]*2+1;
	if(an[n/N])return an[n/N];
	long long ans=1LL*N*N-N+N/2;
	for(int i=2;i<=int(sqrt(N*1.0)+eps);i++){
		ans-=work(N/i);
		if(N/i!=i)ans-=(N/i-N/(i+1))*work(i);
	}
	an[n/N]=ans;
	return ans;
}
int main(){
	Pre(10001);
	a[1]=0;
	for(int i=2;i<=10000;i++)a[i]=a[i-1]+phi[i];
	while(scanf("%d",&n),n){
		memset(an,0,sizeof(an));
		printf("%I64d\n",(work(n)+1)/2);
	}
}

HINT:

1、因为只会查询到n/1,n/2...n/m,所以可以用n/N作为key进行记忆化搜索

2、POJ丧心病狂

3、发现是因为1的欧拉函数我以为是0所以WA了_(:зゝ∠)_-16.2.25GLLG

Category: POJ | Tags: 数论 欧拉函数 | Read Count: 638
Avatar_small
qiancl 说:
2016年1月12日 10:29

%%%%%%%%%%% 所以你是wa了?


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com