HDU 4913

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 的形式。

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

最近状态真是差，写个线段树卡半天，写个几何也RE到现在。早日退役保平安。最简单的思路就是就是假如要求LCM等于 2^a*3^b 的，假如需要求LCM为2^a*3^b 的有多少个，肯定是先找出LCM的2次数<=a,3次数<=b的，然后减掉LCM比这个值小的。我的做法就是把这些数先按照a从小到大，再按照b从小到大排序。然后for一遍。枚举到i的时候，比如第i个数是 \( 2^{a_i}*3^{b_i} \) 那么前面插入的数，2的指数是小于等于 \( a_i \)的。这个时候先统计再前i 个数里面，包含了第i个数的子集对应的答案。既然包含了\(2^{a_i}\) 那么LCM一定是包含\( 2^{a_i} \)的。这样求和的话，其实是可以把这一项提取出来的。假如在3的指数里面，<=j的数有num[j]个。那么需要累加的就是 \[2^{a_i}*3^{j}(2^{num[j]}-2^{num[j-1]}) \] 当然可以先把3的指数离散化一下，然后使用线段树进行维护。需要的操作就是单点加值，区间乘以2，区间求和。维护的就是 \( 3^{j} (2^{num[j]} - 2^{num[j-1]}) \) 当然还有一些细节，比如查询哪个区间，修改哪个区间啥的。具体看代码吧。

/* ***
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 <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 = tmptmp%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].lazyk%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;
}