【AOJ#166】等比数列计数

  • 本文为博主原创，未经许可不得转载

问题转化一下就是求$\sum_{d=1}^{n}[2\sum_{i=1}^{\left \lfloor \sqrt{\left \lfloor \frac{n}{d} \right \rfloor}\right\rfloor}\phi(i)-1]$

这里主要说一下下底分块右端点的确定：

设$k=\left\lfloor\sqrt{\left \lfloor \frac{n}{d} \right \rfloor}\right\rfloor$，则$\sqrt{\left\lfloor\frac{n}{d}\right\rfloor}=k+r_1$，其中$r_1\in[0,1)$

$\left\lfloor\frac{n}{d}\right\rfloor=(k+r_1)^2$，$\frac{n}{d}=(k+r_1)^2+r_2$，其中$r_2\in[0,1)$

$d=\frac{n}{(k+r_1)^2+r_2}$，故$d\in(\left\lceil\frac{n}{(k+1)^2+1}\right\rceil,\left\lfloor\frac{n}{k^2}\right\rfloor]$

所以对于给定的$d$，其分块的右端点就是$\left\lfloor\frac{n}{k^2}\right\rfloor$

另外这道题的加(ka)强(chang)版：（太过毒瘤留坑）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 10000010
using namespace std;
typedef long long ll;
int cnt,prime[MAXN/10];
ll n,ans,phi[MAXN];
bool check[MAXN];
void Init(){
	int N=sqrt(n);  phi[1]=1;
	for(int i=2;i<=N;++i){
		if(!check[i])  prime[++cnt]=i,phi[i]=i-1;
		for(int j=1;j<=cnt&&prime[j]*i<=N;++j){
			check[prime[j]*i]=1;
			if(i%prime[j]==0)  {phi[i*prime[j]]=phi[i]*prime[j]; break;}
			else phi[prime[j]*i]=phi[i]*phi[prime[j]];
		}
	}
	for(int i=1;i<=N;++i)  phi[i]+=phi[i-1];
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	scanf("%lld",&n);  Init();
	for(ll i=1,last;i<=n;i=last+1){
		int k=sqrt(n/i);  last=n/k/k;
		ans+=(2*phi[k]-1)*(last-i+1);
	}
	printf("%lld\n",ans);
	return 0;
}

本文标题:【AOJ#166】等比数列计数

文章作者:chty

发布时间:2018年05月27日 - 21时39分

最后更新:2018年05月27日 - 22时03分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,