题目思路

观察到倍数关系本质构成一张有向无环图,自然考虑动态规划求解。

状态:令$dp_i$ 代表以值$i$为集合最大值的合法集合个数.

转移:

1.直接质因分解，复杂度$O(n\sqrt{m})$ - $m$是值域

2.枚举倍数，复杂度$O(m\log\ m)$ -参考埃式筛

代码

C++

#include <bits/stdc++.h>

using namespace std;

const long long M = 1000000007;
int a[100010], pos[1000010];
long long dp[100010];

int main() {
	memset(pos, -1, sizeof(pos));
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	sort(a, a + n);
	for(int i = 0; i < n; i++) {
		pos[a[i]] = i;
	}
	long long ans = 0;
	for(int i = 0; i < n; i++) {
		int tmp = a[i];
		for(int j = 1; j * j <= tmp; j++) {
			if(tmp % j == 0) {
				if(j != tmp / j && pos[tmp / j] > -1) {
					dp[i] = (dp[i] + dp[pos[tmp / j]]) % M;
				}
				if(pos[j] > -1) {
					dp[i] = (dp[i] + dp[pos[j]]) % M;
				}
			}
		}
		ans += dp[i];
		ans %= M;
		dp[i]++;
	}
	cout << ans;
}

题目内容

米小游是一位对数学问题十分着迷的年轻人。最近，他参加了一场数学竞赛，其中有一道问题要求他计算一个大小为 $n$ 的集合中元素数量大于 $1$ 的子集，满足子集内的元素两两之间互为倍数关系的个数。但是在考场的时候米小游并没有想出来如何解决，考试完了回来以后他为了这个题废寝忘食，一直在思考这个问题，也没有很大的进展，作为他最好的朋友的你能不能帮他想一想这个题目要如何解决？

由于子集数量可能过大，请对 $10^9+7$ 取模。

输入描述

第一行输入一个正整数 $n$ ，代表集合大小。

第二行输入 $n$ 个正整数 $a_i$ ，代表集合的元素。

$1\le n \le 10^5$

$1 \le a_i \le 10^6$

输出描述

一个整数，代表满足题意的子集数量对 对 $10^9+7$ 取模的值。

样例

输入

5
1 2 3 4 5

输出

6

样例解释

共有6个合法的子集：

{1,2},{1,3},{1,4},{1,5},{1,2,4},{2,4}