# Least common multiple

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

Problem Description

bobo has an integer set S={x1,x2,…,xn}, where xi=2ai * 3bi.For each non-empty subsets of S, bobo added the LCM (least common multiple) of the subset up. Find the sum of LCM modulo (109+7).

Input

The input consists of several tests. For each tests:The first line contains n (1≤n≤105). Each of the following n lines contain 2 integers ai,bi (0≤ai,bi≤109).

Output

For each tests:A single integer, the value of the sum.

Sample Input

2 0 1 1 0 3 1 2 2 1 1 2

Sample Output

11 174

Author

Xiaoxu Guo (ftiasch)

Source

2014 Multi-University Training Contest 5

### 题意很清楚，也很容易理解。LCM一定是2^i 3^j 的形式。

#### 这题的关键是转化的过程，将问题转化为线段树解决。

/* ***
Author :kuangbin
Created Time :2014/8/5 19:08:16
File Name :E:\2014ACM\比赛\2014多校训练\2014多校5\HDU4913.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include

#include

#include

#include

#include

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const int MOD = 1e9+7;
const int MAXN = 100010;
struct Node
{
int x,y;
void input()
{
scanf(“%d%d”,&x,&y);
}
}node[MAXN];
bool cmp(Node a,Node b)
{
if(a.x != b.x)return a.x < b.x;
else return a.y < b.y;
}
int tot;
int c[MAXN];
int lowbit(int x)
{
return x&(-x);
}
void add(int i,int val)
{
while(i <= tot)
{
c[i] += val;
i += lowbit(i);
}
}
int sum(int i)
{
int s = 0;
while(i)
{
s += c[i];
i -= lowbit(i);
}
return s;
}

int b[MAXN];

long long pow_m(long long a,long long n)
{
long long ret = 1;
long long tmp = a;
while(n)
{
if(n&1)ret = rettmp%MOD;
tmp = tmp
tmp%MOD;
n >>= 1;
}
return ret;
}

struct SEGNODE
{
int l,r;
int val;
long long sum;
long long lazy;
}segTree[MAXN<<2];
void push_up(int i)
{
segTree[i].sum = segTree[i<<1].sum + segTree[(i<<1)|1].sum;
if(segTree[i].sum >= MOD)segTree[i].sum -= MOD;
}
void Update(int i,int k )
{
segTree[i].sum = segTree[i].sumk%MOD;
segTree[i].lazy = segTree[i].lazy
k%MOD;
}
void push_down(int i)
{
if(segTree[i].lazy != 1)
{
Update(i<<1,segTree[i].lazy);
Update((i<<1)|1,segTree[i].lazy);
segTree[i].lazy = 1;
}
}
void build(int i,int l,int r)
{
segTree[i].l = l;
segTree[i].r = r;
segTree[i].sum = 0;
segTree[i].lazy = 1;
if(l == r)
{
segTree[i].val = pow_m(3,b[l]);
return;
}
int mid = (l+r)/2;
build(i<<1,l,mid);
build((i<<1)|1,mid+1,r);
}
void ADD(int i,int k)
{
if(segTree[i].l == k && segTree[i].r == k)
{
int tmp = sum(k);
segTree[i].sum += pow_m(2,tmp)*segTree[i].val%MOD;
if(segTree[i].sum >= MOD)segTree[i].sum-=MOD;
add(k,1);
return;
}
int mid = (segTree[i].l + segTree[i].r)/2;
push_down(i);
if(k <= mid)ADD(i<<1,k);
else ADD((i<<1)|1,k);
push_up(i);
}
void CHANGE(int i,int l,int r)
{
if(r < l)return;
if(segTree[i].l == l && segTree[i].r == r)
{
Update(i,2);
return;
}
int mid = (segTree[i].l + segTree[i].r)/2;
push_down(i);
if(r <= mid)CHANGE(i<<1,l,r);
else if(l > mid)CHANGE((i<<1)|1,l,r);
else
{
CHANGE(i<<1,l,mid);
CHANGE((i<<1)|1,mid+1,r);
}
push_up(i);
}
long long sum(int i,int l,int r)
{
if(segTree[i].l == l && segTree[i].r == r)
return segTree[i].sum;
int mid = (segTree[i].l+segTree[i].r)/2;
push_down(i);
if(r <= mid)return sum(i<<1,l,r);
else if(l > mid)return sum((i<<1)|1,l,r);
else
{
return (sum(i<<1,l,mid)+sum((i<<1)|1,mid+1,r))%MOD;
}
}

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int n;
while(scanf(“%d”,&n) == 1)
{
for(int i = 0;i < n;i++)
{
node[i].input();
b[i] = node[i].y;
}
sort(node,node+n,cmp);
sort(b,b+n);
tot = unique(b,b+n)-b;
map<int,int>mp;
for(int i = 0;i < tot;i++)mp[b[i]] = i+1;
for(int i = tot;i > 0;i–)
b[i] = b[i-1];
memset(c,0,sizeof(c));
long long ans = 0;
build(1,1,tot);
for(int i = 0;i < n;i++)
{
int id = mp[node[i].y];
long long tmp = pow_m(2,node[i].x);
tmp = tmp (sum(1,id,tot) + pow_m(3,node[i].y))%MOD;
tmp = (tmp%MOD+MOD)%MOD;
ans += tmp;
if(ans >= MOD)ans -= MOD;
int nn = sum(id-1);
ans += pow_m(2,node[i].x)
(pow_m(2,nn) - 1)%MOD*pow_m(3,node[i].y)%MOD;
if(ans >= MOD)ans -= MOD;
ADD(1,id);
CHANGE(1,id+1,tot);
}
printf(“%d\n”,(int)ans);
}
return 0;
}

------ 本文结束------
• 本文作者： kuangbin
• 本文链接： 328.html
• 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！
0%