题目链接:
戳我
题目大意:
f(l, r)代表一个l,r区间内,符合任选i,j (l <= j <= r && j != i)
,有$a{i}$ % $a{j}$ != 0的i的个数
求 $\sum{i = 1}^n \sum{j = i}^n f(i, j) mod(10^9+7)$
样例解释
5
即为n,代表有n个数,n <= $10^5$1 2 3 4 5
分别为上面的 n 个数,0 < $a_{i}$ <= 10000
f(1,1) = {1} = 1; f(1,2) = {1} = 1; f(1,3) = {1} = 1; f(1,4) = {1} = 1; f(1,5) = {1} = 1
f(2,2) = {2} =1; f(2,3) = {2,3} = 2; f(2,4) = {2,3} = 2; f(2,5) = {2,3,5} = 3
f(3,3) = {3} = 1; f(3,4) = {3,4} = 2; f(3,5) = {3,4,5} = 3;
f(4,4) = {4} = 1; f(4, 5) = {4,5} = 2;
f(5,5) = {5} = 1;故所有加起来为23
解题思路
分析:数组长度为$10^5$,而每个数不超多 10000
假设一个数的位置是 pos 值为x
,那个在x
左侧和x最近的属于x的因子的位置是l,在x
右侧和x最近的属于x因子的位置是r,那么在(l+1, r-1)
这个区间内,任选左区间一个位置ll,在任选右区间一个位置rr,那么x必为此区间符合条件的一个数
故 $num = (x-l)*(r-x)$
只需枚举每一个位置,极其l,r即可
思路:
可以先预处理10000个数的每个数的因子,在枚举每一个位置的时候即可知道最左的因子和最右的因子了
代码:
452ms1
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87//Author LJH
//www.cnblogs.com/tenlee
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define clc(a, b) memset(a, b, sizeof(a))
using namespace std;
const int inf = 0x3f;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
const long long mod = 1e9+7;
int a[maxn], ha[maxn], l[maxn], r[maxn], pre[maxn];
vector<int> v[maxn];
void Init()
{
v[1].push_back(1);
for(int i = 2; i <= maxn; i++)
{
for(int j = 2; i*j <= maxn; j++)
{
v[j*i].push_back(i);
}
v[i].push_back(1);
v[i].push_back(i);
}
}
int main()
{
//freopen("1001.in", "r", stdin);
int n, i, j, k = 0;
long long ans;
Init();
while(~scanf("%d", &n))
{
for(i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
clc(pre, 0);
for(i = 1; i <= n; i++)
{
l[i] = 1;
k = a[i];
for(j = 0; j < (int)v[k].size(); j++)
{
if(pre[v[k][j]] != 0)
{
l[i] = max(l[i], pre[v[k][j]] + 1);
}
}
//if(a[i] == a[i-1]) l[i] = i;
pre[a[i]] = i;
}
clc(pre, 0);
for(i = n; i > 0; i--)
{
r[i] = n;
k = a[i];
for(j = 0; j < (int)v[k].size(); j++)
{
if(pre[v[k][j]] != 0)
{
r[i] = min(r[i], pre[v[k][j]] - 1);
}
}
//if(a[i]==a[i+1]) r[i] = i;
pre[a[i]] = i;
}
ans = 0;
for(i = 1; i <= n; i++)
{
ans = (ans + (long long)( i - l[i] + 1) * (long long)(r[i] - i + 1) % mod) % mod;
if(ans > mod) ans -= mod;
}
printf("%lld\n", ans % mod);
}
return 0;
}
标程代码:
1232ms1
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89#include<cstdio>
#include<iostream>
#include<vector>
#define N 100010
#define P 1000000007
using namespace std;
int n,i,a[N],j,t,q[N];
int l[N],tmp,r[N];
long long a1,a2,ans;
vector<int> vec[10010];
int main()
{
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
while (scanf("%d",&n)!=EOF)
{
for (i=101;i<=10000;i++)
vec[i].clear();
for (i=1;i<=n;i++)
{
l[i]=0;
r[i]=n+1;
scanf("%d",&a[i]);
if (a[i]>100)
vec[a[i]].push_back(i);
}
for (j=1;j<=100;j++)
{
tmp=0;
for (i=1;i<=n;i++)
{
if (a[i]%j==0) l[i]=max(l[i],tmp);
if (a[i]==j)
tmp=i;
}
tmp=n+1;
for (i=n;i>=1;i--)
{
if (a[i]%j==0) r[i]=min(r[i],tmp);
if (a[i]==j)
tmp=i;
}
}
for (i=101;i<=10000;i++)
q[i]=0;
for (i=1;i<=n;i++)
if (a[i]>100)
{
for (j=a[i];j<=10000;j=j+a[i])
while ((q[j]<vec[j].size())&&(vec[j][q[j]]<i))
{
r[vec[j][q[j]]]=min(r[vec[j][q[j]]],i);
if ((q[j]<vec[j].size()-1)&&(vec[j][q[j]+1]<i))
q[j]++;
else
break;
}
}
for (i=101;i<=10000;i++)
q[i]=vec[i].size()-1;
for (i=n;i>=1;i--)
if (a[i]>100)
{
for (j=a[i];j<=10000;j=j+a[i])
while ((q[j]>=0)&&(vec[j][q[j]]>i))
{
l[vec[j][q[j]]]=max(l[vec[j][q[j]]],i);
if ((q[j]>0)&&(vec[j][q[j]-1]>i))
q[j]--;
else
break;
}
}
ans=0;
for (i=1;i<=n;i++)
{
a1=r[i]-i;
a2=i-l[i];
ans=(ans+a1*a2)%P;
}
printf("%I64d\n",ans);
}
}