题目描述：（暂不公开）
这道题可以考虑直接统计答案。 这里附上一个考场时对拍的一个去不合法的代码。 好像写错了。然后拍了好久结果发现对拍错了。
对拍代码：（大佬们顺便帮我看看哪里写错了，蟹蟹）
#include <cstdio> #include <cstring> using namespace std; typedef long long ll; const int N = 100010; inline void read(int &x) { char ch = getchar(); x = 0; for(;ch < '0' || ch > '9';) ch = getchar(); for(;ch >= '0' && ch <= '9';) x = x * 10 + (ch ^ '0'), ch = getchar(); } struct Edge{ int to,nxt; } g[N << 1]; int last[N],cnt = 0; int n,K,a[N],buc[N],tot; ll ans; void add(int u,int v) { g[++cnt] = (Edge){ v,last[u] }, last[u] = cnt; } ll calc(int x) { ll ret = 0; for(int i = last[x];i;i = g[i].nxt) ret += n - g[i].to + 1; return ret; } int main() { read(n), read(K); ans = n * (n - 1) / 2; for(int i = 1;i <= n; ++ i) read(a[i]); for(int i = n;i; -- i) { if(a[i] > K) { buc[K + 1] += n - i + 1; int p = a[i] - K; for(int d = 1;d * d < p; ++ d) if(p % d == 0) { ans -= buc[d]; if(p / d != d) ans -= buc[p / d]; } } else if(a[i] == K) ans -= buc[K + 1], buc[K] += n - i + 1; else buc[a[i]] += n - i + 1; } printf("%lld",ans); return 0; }后来写了个暴力发现对拍错了。。。
正解并不难。 从后往前扫，先用一个桶来记录每一个数最晚出现的位置。 我们可以用两个指针。代表最早出现与 i i i不合法的数的位置。 l l l为辅助，然后 r r r是用来统计答案的。 然后就这样啊。
#include <cstdio> #include <cstring> using namespace std; typedef long long ll; const ll N = 100010; inline ll min(ll a,ll b) { return a < b ? a : b; } inline void read(ll &x) { char ch = getchar(); x = 0; for(;ch < '0' || ch > '9';) ch = getchar(); for(;ch >= '0' && ch <= '9';) x = x * 10 + (ch ^ '0'), ch = getchar(); } ll n,m,a[N],l,r,buc[N],ans; int main() { freopen("drink.in","r",stdin); freopen("drink.out","w",stdout); read(n), read(m); l = n, r = l + 1; for(int i = 1;i <= n; ++ i) read(a[i]); memset(buc,0x3f,sizeof buc); for(int i = n;i; -- i) { if(a[i] == m) r = min(r,l); else { for(int j = 1;j * j <= a[i] - m; ++ j) { if((a[i] - m) % j) continue; if(j > m) r = min(buc[j],r); if((a[i] - m) / j > m) r = min(buc[(a[i] - m) / j],r); } } if(a[i] > m) l = i; buc[a[i]] = i, ans += r - i; } printf("%lld",ans); fclose(stdin); fclose(stdout); return 0; }