HDU 4913 Least common multiple 解题报告（线段树）Least common multiple

125 阅读 0 评论 83 点赞

我是靠谱客的博主动听短靴，这篇文章主要介绍HDU 4913 Least common multiple 解题报告（线段树）Least common multiple，现在分享给大家，希望可以做个参考。

Least common multiple

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 83 Accepted Submission(s): 25

Problem Description

bobo has an integer set S={x ₁,x ₂,…,x _n}, where x _i=2 ^ai * 3 ^bi.

For each non-empty subsets of S, bobo added the LCM (least common multiple) of the subset up. Find the sum of LCM modulo (10 ⁹+7).

Input

The input consists of several tests. For each tests:

The first line contains n (1≤n≤10 ⁵). Each of the following n lines contain 2 integers a _i,b _i (0≤a _i,b _i≤10 ⁹).

Output

For each tests:

A single integer, the value of the sum.

Sample Input

复制代码

Sample Output

复制代码

Author

Xiaoxu Guo (ftiasch)

Source

2014 Multi-University Training Contest 5

解题报告：思路和官方的思路是一样的。使用线段树维护 b 这边的和。

官方解题报告路径：blog.sina.com.cn/s/blog_6bddecdc0102uz53.html

代码如下：

复制代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <iomanip>
using namespace std;
#define ff(i, n) for(int i=0;i<(n);i++)
#define fff(i, n, m) for(int i=(n);i<=(m);i++)
#define dff(i, n, m) for(int i=(n);i>=(m);i--)
#define bit(n) (1LL<<(n))
typedef long long LL;
typedef unsigned long long ULL;
const LL inf=1e15;
void work();
int main()
{
#ifdef ACM
freopen("input.in", "r", stdin);
//
freopen("input.in", "w", stdout);
#endif // ACM
work();
}
/***************************************************/
const int maxn = 111111;
const int mod = 1e9+7;
int n;
struct Node
{
int a, b;
bool operator<(const Node & cmp) const
{
return a == cmp.a ? b < cmp.b : a < cmp.a;
}
} node[maxn];
double bb[maxn];
int tot;
int powMod(LL a, int b)
{
LL res = 1;
while(b)
{
if(b&1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
#define lson l, m, pos<<1
#define rson m+1, r, pos<<1|1
#define defm int m = (l+r)/2
int sum[maxn<<2];
int mul[maxn<<2];
void updateFather(int pos)
{
sum[pos] = (sum[pos<<1] + sum[pos<<1|1]) % mod;
}
void updateSon(int pos)
{
if(mul[pos] > 1)
{
mul[pos<<1] = (LL)mul[pos<<1] * mul[pos] % mod;
sum[pos<<1] = (LL)sum[pos<<1] * mul[pos] % mod;
mul[pos<<1|1] = (LL)mul[pos<<1|1] * mul[pos] % mod;
sum[pos<<1|1] = (LL)sum[pos<<1|1] * mul[pos] % mod;
mul[pos] = 1;
}
}
void updateP(int p, int v, int l, int r, int pos)
{
if(l == r)
{
sum[pos] = (LL)v * mul[pos] % mod;
return ;
}
updateSon(pos);
defm;
if(p<=m)
updateP(p, v, lson);
else
updateP(p, v, rson);
updateFather(pos);
}
void update(int L, int R, int l, int r, int pos)
{
if(L<=l && r<=R)
{
mul[pos] = mul[pos] * 2 % mod;
sum[pos] = sum[pos] * 2 % mod;
return;
}
updateSon(pos);
defm;
if(L<=m)
update(L, R, lson);
if(m<R)
update(L, R, rson);
updateFather(pos);
}
int query(int L, int R, int l, int r, int pos)
{
if(L<=l && r<=R)
return sum[pos];
updateSon(pos);
defm;
return ((L<=m?query(L,R,lson):0) + (m<R?query(L,R,rson):0))%mod;
}
void work()
{
while(scanf("%d", &n) == 1)
{
tot = 0;
ff(i, n) scanf("%d%d", &node[i].a, &node[i].b), bb[tot++] = node[i].b;
sort(node, node + n);
sort(bb, bb + tot);
double sub = 0.999999;
double eve = 0.000001;
memset(sum, 0, sizeof(sum));
ff(i, maxn<<2) mul[i] = 1;
LL ans = 0;
ff(i, n)
{
LL now = powMod(2, node[i].a);
int pos = lower_bound(bb, bb+tot, node[i].b) - bb;
bb[pos] -= sub, sub -= eve;
updateP(pos, powMod(3, node[i].b), 0, tot, 1);
ans += now * query(pos, tot, 0, tot, 1) % mod;
update(pos+1, tot, 0, tot, 1);
}
printf("%dn", ans%mod);
}
}

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <iomanip>
using namespace std;
#define ff(i, n) for(int i=0;i<(n);i++)
#define fff(i, n, m) for(int i=(n);i<=(m);i++)
#define dff(i, n, m) for(int i=(n);i>=(m);i--)
#define bit(n) (1LL<<(n))
typedef long long LL;
typedef unsigned long long ULL;
const LL inf=1e15;
void work();
int main()
{
#ifdef ACM
freopen("input.in", "r", stdin);
//
freopen("input.in", "w", stdout);
#endif // ACM
work();
}
/***************************************************/
const int maxn = 111111;
const int mod = 1e9+7;
int n;
struct Node
{
int a, b;
bool operator<(const Node & cmp) const
{
return a == cmp.a ? b < cmp.b : a < cmp.a;
}
} node[maxn];
double bb[maxn];
int tot;
int powMod(LL a, int b)
{
LL res = 1;
while(b)
{
if(b&1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
#define lson l, m, pos<<1
#define rson m+1, r, pos<<1|1
#define defm int m = (l+r)/2
int sum[maxn<<2];
int mul[maxn<<2];
void updateFather(int pos)
{
sum[pos] = (sum[pos<<1] + sum[pos<<1|1]) % mod;
}
void updateSon(int pos)
{
if(mul[pos] > 1)
{
mul[pos<<1] = (LL)mul[pos<<1] * mul[pos] % mod;
sum[pos<<1] = (LL)sum[pos<<1] * mul[pos] % mod;
mul[pos<<1|1] = (LL)mul[pos<<1|1] * mul[pos] % mod;
sum[pos<<1|1] = (LL)sum[pos<<1|1] * mul[pos] % mod;
mul[pos] = 1;
}
}
void updateP(int p, int v, int l, int r, int pos)
{
if(l == r)
{
sum[pos] = (LL)v * mul[pos] % mod;
return ;
}
updateSon(pos);
defm;
if(p<=m)
updateP(p, v, lson);
else
updateP(p, v, rson);
updateFather(pos);
}
void update(int L, int R, int l, int r, int pos)
{
if(L<=l && r<=R)
{
mul[pos] = mul[pos] * 2 % mod;
sum[pos] = sum[pos] * 2 % mod;
return;
}
updateSon(pos);
defm;
if(L<=m)
update(L, R, lson);
if(m<R)
update(L, R, rson);
updateFather(pos);
}
int query(int L, int R, int l, int r, int pos)
{
if(L<=l && r<=R)
return sum[pos];
updateSon(pos);
defm;
return ((L<=m?query(L,R,lson):0) + (m<R?query(L,R,rson):0))%mod;
}
void work()
{
while(scanf("%d", &n) == 1)
{
tot = 0;
ff(i, n) scanf("%d%d", &node[i].a, &node[i].b), bb[tot++] = node[i].b;
sort(node, node + n);
sort(bb, bb + tot);
double sub = 0.999999;
double eve = 0.000001;
memset(sum, 0, sizeof(sum));
ff(i, maxn<<2) mul[i] = 1;
LL ans = 0;
ff(i, n)
{
LL now = powMod(2, node[i].a);
int pos = lower_bound(bb, bb+tot, node[i].b) - bb;
bb[pos] -= sub, sub -= eve;
updateP(pos, powMod(3, node[i].b), 0, tot, 1);
ans += now * query(pos, tot, 0, tot, 1) % mod;
update(pos+1, tot, 0, tot, 1);
}
printf("%dn", ans%mod);
}
}