看心情填坑

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

上次听叶队说欧拉函数前缀和有O(n^2/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优，那么可得k^0.5>n/k-n/(k+1)，即k^1.5(k+1)>n,可以近似得到k^2.5>n，也就是当k=n^0.4答案最优，即m取n^0.6时答案最优（叶队说是n^2/3，不明),时间复杂度为O(n^0.6+\(\sum_{k=1}^{{n}^{0.4}}\sqrt{k}\))(然而这个东西显然小于n^0.6反正能过10^9)空间复杂度O(m)=O(n^0.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