盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码
  5. 更新日志

HDU 5288 OO’s Sequence(数学)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5288

题意

在闭区间[l,r]内有一个数a[i],a[i]不能整除除去自身以外的其他的数,f(l,r)表示在这区间内a[i]这样的数的个数,,现给你n个数,求所有区间的f(l,r)的和。
其中 n ≤ 100000; a[i] ≤ 10000

思路

对于一个数a[i],找到两端离他最近的因子l[i], r[i],那么它能够贡献的答案就是(r[i] - i) * (i - l[i])。枚举每一个数的因子,然后用该数更行l,r数组。

代码

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
typedef long long ll;
const int INF = 0x3f3f3f3f;
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e5 + 100;
int a[N], l[N], r[N], n, p[10010];
ll ans;
int main () {
while(~scanf("%d", &n)) {
for (int i = 0; i < n; i++) scanf("%d", a + i);
memset(p, -1, sizeof(p));
ans = 0;
p[a[0]] = 0, l[0] = 0;
for (int i = 1; i < n; i++) {
int q = sqrt(a[i] + 0.5);
l[i] = -1;
for (int j = 1; j <= q; j++) if (a[i] % j == 0){
l[i] = max(l[i], p[a[i] / j]);
l[i] = max(l[i], p[j]);
}
if (l[i] == -1) l[i] = 0;
else l[i]++;
p[a[i]] = i;
//cout<<l[i]<<endl;
}
memset(p, INF, sizeof(p));
p[a[n - 1]] = n - 1, r[n - 1] = n - 1;
ans = (n - 1 - l[n - 1] + 1) * (r[n - 1] - (n - 1) + 1);
//cout<<ans<<endl;
for (int i = n - 2; i >= 0; i--) {
int q = sqrt(a[i] + 0.5);
r[i] = INF;
for (int j = 1; j <= q; j++) if (a[i] % j == 0) {
r[i] = min(r[i], p[a[i] / j]);
r[i] = min(r[i], p[j]);
}
if (r[i] == INF) r[i] = n - 1;
else r[i]--;
p[a[i]] = i;
//cout<<r[i]<<endl;
ans =(ans + (ll)(i - l[i] + 1) * (r[i] - i + 1)) % mod;
}
printf("%I64d\n", ans);
}
return 0;
}

更新日志

  • 14110337 2015-07-22 15:23:36 Accepted 5288 967MS 2788K 1324 B G++ SIO__Five