【每日一题】P1403 [AHOI2005]约数研究

文章目录

• 前言
• 解题思路
• • f ( i ) = n / i f(i)=n/i f(i)=n/i
  • 以n=12为例，约数表如下：
• AC代码
• 总结

---

前言

坚持每天做一道算法题，每天学一点数据结构与算法，写思路和题解来加深自己的印象。

---

P1403 [AHOI2005]约数研究

---

解题思路

找规律：在1~n中含有“2”这个因子的数有n/2个，3有n/3个，以此类推，公式就出来了。

f ( i ) = n / i f(i)=n/i f(i)=n/i 以n=12为例，约数表如下：

	1	2	3	4	5	6	7	8	9	10	11	12
1	1	1	1	1	1	1	1	1	1	1	1	1
2		2		2		2		2		2		2
3			3			3			3			3
4				4				4				4
5					5					5
6						6						6
7							7
8								8
9									9
10										10
11											11
12												12
	1	2	2	3	2	4	2	4	3	4	2	6
SUM	1	3	5	8	10	14	16	20	23	27	29	35

---

AC代码

#include 
using namespace std;

int n;
long long int res;

void solve(int n) {
	for(int i = 1; i <= n; i++)	res += n / i;
}

int main (void) {
	scanf("%d", &n);
	solve(n);
	printf("%lld", res);
	return 0;
}

---

总结

感觉自己有些投机取巧解了这道题，但是看了大佬们的题解算是彻底理解了这道题。
这道题可以暴力，但貌似不能纯暴力，要用筛法。代码如下：

#include 
using namespace std;

int n;
int a[10000001];
long long int res;

void solve(int n) {
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j += i) a[j]++; // i翻倍，其倍数j一定含有因子i
		res += a[i];
	}
}

int main (void) {
	scanf("%d", &n);
	solve(n);
	printf("%lld", res);
	return 0;
}