调和级数

简介

$1$到$n$自然数的倒数和大约是 $\log n$
$$n / 1 + n / 2 + n / 3 + .. + n / n = n \log n$$

$1$到$n$质数的倒数和大约是 $\log \log n$
$$n / 2 + n / 3 + n / 5 + n / 7 + ... = n \log \log n$$

都是发散的。
Divergent series

时间复杂度

一些算法的时间复杂度是调和级数，所以不会超时

参考题目

P2926 [USACO08DEC]Patting Heads S

https://www.luogu.com.cn/problem/P2926

题目描述

It's Bessie's birthday and time for party games! Bessie has instructed the N (1 <= N <= 100,000) cows conveniently numbered 1..N to sit in a circle (so that cow i [except at the ends] sits next to cows i-1 and i+1; cow N sits next to cow 1). Meanwhile, Farmer John fills a barrel with one billion slips of paper, each containing some integer in the range 1..1,000,000.

Each cow i then draws a number A_i (1 <= A_i <= 1,000,000) (which is not necessarily unique, of course) from the giant barrel. Taking turns, each cow i then takes a walk around the circle and pats the heads of all other cows j such that her number A_i is exactly

divisible by cow j's number A_j; she then sits again back in her original position.

The cows would like you to help them determine, for each cow, the number of other cows she should pat.

输入格式

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains a single integer: A_i

输出格式

* Lines 1..N: On line i, print a single integer that is the number of other cows patted by cow i.

样例 #1

样例输入 #1

5 
2 
1 
2 
3 
4 

样例输出 #1

2 
0 
2 
1 
3 

提示

The 5 cows are given the numbers 2, 1, 2, 3, and 4, respectively.

The first cow pats the second and third cows; the second cows pats no cows; etc.

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int a[100020];
int c[1000020];
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
		c[a[i]]++;
	}
	for (int i = 1000000; i > 0; i--)
	{
		for (int j = 2 * i; j <= 1000000; j += i)
		{
			c[j] += c[i];
		}
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d\n", c[a[i]] - 1);
	}
	return 0;
}

题解

时间复杂度是调和级数

所以不会超时