D - 神奇的%系列二
Problem Description
在计算机的世界里，%不是百分比，而是除法取余哟！
比如：
4 % 2 = 0
5 % 3 = 2
现在，给你 N 个正整数的序列，a[1],a[2]...a[i]...a[n]。
有 Q 个询问：
L R X ，问下标区间在[L, R]之间的数a[i]，有几个数能整除 X（即 X
% a[i] == 0，且L ≤ i ≤ R）
Input
输入有多组数据。(≤ 25)
对于每组数据：
第一行：N（表示 N 个元素，1
≤ N ≤ 100000）
第二行：a[1] a[2] ... a[n]（表示序列的 N 个元素，1 ≤ a[i] ≤ 100000）
第三行：Q（表示 Q 个询问，1 ≤ Q ≤ 100000）
接下来 Q 行，每行三个整数：L R X (1 ≤ L ≤ R ≤ N，1 ≤ X ≤ 100000)
Output
对于每个询问，输出一个数。
表示下标区间在[L, R]之间的数，有几个能整除 X 的数
Sample Input
5 1 2 3 4 5 3 2 4 6 1 5 2 1 5 60
Sample Output
2 2 5
D题
本题要求N个数的序列中，下标在[L,R]区间内的a[i]，有几个能整除X （ X % a[i] == 0 ）。
首先我要告诉你，关键的突破口在于a[i]<=100000。
而100000以内的数最多有127个因子。（说到这里，知道怎么做了吧？）
嗯？怎么处理区间[L,R]？
你只要记录[1,R]以及[1,L-1]区间内的数有几个能整除X。那么b-a，就是[L,R]区间的个数。
那么如何处理Q个询问呢？？？
对于Q个询问，拆成两个单点询问，即看成 [1,L-1] 和 [1,R] 能整除X的有几个即可。
[1,L-1]询问的符号标记为sgn=-1；
[1,R]询问的符号标记为sgn=1。
至于[1,B]区间内能整除X的数，你总会求了吧？
for(int i=1;i<=n;i++) {
cnt[a[i]]++; //记录有几个a[i]
num=getnum(X); //求[1,i]区间内的有几个a[i]可以整除X
}
int getnum(int X) {
for(遍历X的因子: fac) //最多127个
ans+=cnt[fac];
return ans;
}
所以对于每个询问，最坏复杂度为遍历了127个因子。
故最坏复杂度为 N + 127*Q*2（每个询问遍历两次）
|
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
#include#include#include#include#includeusingconstvector<int>vector<int, int>intintintintvoid for(int pos[i].clear(); cnt[i] ans[i] }}inlineint int for(int ret } return}int for(int for(int for(int fac[j].push_back(i); } } while(scanf("%d",&n)!=EOF) init(); for(int scanf("%d", } scanf("%d",&m); for(int int scanf("%d%d%d", pos[l pos[r].push_back( } for(int cnt[num[i]]++; for(intint)pos[i].size(); int int int if(ans[idx] else } } for(int printf("%d\n", } } return} |