题意
给一个长n数组hi和k，对每个hi求有几个hj满足是hi % hj == k。 hi 最大1e6
思路
求 hi % hj == k
等价于求 (hi - k) % hj == 0
这中间就有许多隐含条件：
hj > khi >= k
如果 hi == k, ans[i] 就是求多少 j 满足 hj > k如果 hi > k, ans[i] 就是有多少 j 满足 (hi - k) % hj == 0 并且 hj 不是 hi 的因子
考虑数值范围不大，可以用筛法，统计 hi 的个数 cnt[hi]，加给 hi 所有的倍数 cnt[d*hi]。
由于除数hj必须要大于k，所以我们的筛的起点从k + 1开始。
基于这个特性，我们可以通过cnt[hi - k] 得到合法除数hj的个数，并且已经保证hj不是hi的因子。
因为已保证 (hi - k) % hj == 0 且 hj > k k % hj > 0 (hi - k) % hj + k % hj > 0 hi % hj > 0
K是0的时候要特判一下， 因为此时就是求每个数的因子个数。
复杂度，根据调和级数，可得是
O
(
N
l
o
g
(
N
)
)
O(Nlog(N))
O(Nlog(N)) （1e6数量级）
代码
int n
, k
;
int h
[MAXN
];
int v
[MAXN
];
int ans
[MAXN
];
int cnt
[MAXN
];
int maxhi
= 0;
int moreThanK
= 0;
inline void read(int &x
) {
char ch
;
bool flag
= false;
for (ch
= getchar(); !isdigit(ch
); ch
= getchar())if (ch
== '-') flag
= true;
for (x
= 0; isdigit(ch
); x
= x
* 10 + ch
- '0', ch
= getchar());
x
= flag
? -x
: x
;
}
void solve(int kaseId
= -1) {
read(n
);
read(k
);
for (int i
= 1; i
<= n
; ++i
) {
read(h
[i
]);
v
[h
[i
]]++;
moreThanK
+= int(h
[i
] > k
);
maxhi
= max(maxhi
, h
[i
]);
}
for (int i
= k
+ 1; i
<= maxhi
; ++i
) {
if (v
[i
] == 0) continue;
for (int j
= i
; j
<= maxhi
; j
+= i
) {
cnt
[j
] += v
[i
];
}
}
if (k
== 0) {
for (int i
= 1; i
<= n
; ++i
) {
ans
[i
] = cnt
[h
[i
]] - 1;
}
} else {
for (int i
= 1; i
<= n
; ++i
) {
if (h
[i
] < k
) {
ans
[i
] = 0;
} else if (h
[i
] == k
) {
ans
[i
] = moreThanK
;
} else if (h
[i
] > k
) {
ans
[i
] = cnt
[h
[i
] - k
];
}
}
}
for (int i
= 1; i
<= n
; ++i
) {
printf("%d%c", ans
[i
], " \n"[i
== n
]);
}
}
