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

118 阅读 0 评论 78 点赞

我是靠谱客的博主动听短靴，最近开发中收集的这篇文章主要介绍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


11
174

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);
}
}