2014マルチキャリブレーション5(1003)hdu 4913(セグメントツリー区間操作)
3805 ワード
Least common multiple
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 451 Accepted Submission(s): 151
Problem Description
bobo has an integer set S={x
1,x
2,…,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
9+7).
Input
The input consists of several tests. For each tests:
The first line contains n (1≤n≤10
5). Each of the following n lines contain 2 integers a
i,b
i (0≤a
i,b
i≤10
9).
Output
For each tests:
A single integer, the value of the sum.
Sample Input
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 451 Accepted Submission(s): 151
Problem Description
bobo has an integer set S={x
1,x
2,…,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
9+7).
Input
The input consists of several tests. For each tests:
The first line contains n (1≤n≤10
5). Each of the following n lines contain 2 integers a
i,b
i (0≤a
i,b
i≤10
9).
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
题意：RT
思路：最小公倍数只能是形如2^a * 3^b，而每次求一种最小公倍数 2^i * 3^j 的和只需要考虑小于等于i 和 j 的集合总数就好了，这个计数可以用线段树来完成，按a从小到大的顺
序将b插入线段树（注意b要先离散化），对于相同的a在插入b的时候也要按照b从小到大插入，这是为了保证后面比b大的数还是在a之前插入的，然后可以用两个数组分别维护
小于等于b的集合数 f[o] 和 小于b的集合数 ff[o]，然后f[o]-ff[o]就是此时等于b的集合数了，累加就好了，这题也是把我恶心了好久，sad~~
#include
#include
#include
#include
#include
using namespace std;
#define maxn 100010
#define lson l,m,o<<1
#define rson m+1,r,o<<1|1
#define mod (1000000000+7)
typedef __int64 ll;
ll f[maxn<<2];
ll ff[maxn<<2];
ll tree[maxn<<2];
ll treef[maxn<<2];
struct node{
int a;
int b;
ll ax;
ll bx;
};
node vex[maxn];
int n;
void pushdown(int o)
{
if(f[o]!=1)
{
f[o<<1]=f[o<<1]*f[o]%mod;
f[o<<1|1]=f[o<<1|1]*f[o]%mod;
tree[o<<1]=tree[o<<1]*f[o]%mod;
tree[o<<1|1]=tree[o<<1|1]*f[o]%mod;
f[o]=1;
}
if(ff[o]!=1)
{
ff[o<<1]=ff[o<<1]*ff[o]%mod;
ff[o<<1|1]=ff[o<<1|1]*ff[o]%mod;
treef[o<<1]=treef[o<<1]*ff[o]%mod;
treef[o<<1|1]=treef[o<<1|1]*ff[o]%mod;
ff[o]=1;
}
}
void pushup(int o)
{
tree[o]=(tree[o<<1]+tree[o<<1|1])%mod;
treef[o]=(treef[o<<1]+treef[o<<1|1])%mod;
}
void build(int l,int r,int o)
{
f[o]=ff[o]=1;
if(l==r){
tree[o]=treef[o]=0;
return;
}
int m=l+r>>1;
build(lson);
build(rson);
pushup(o);
}
void insert1(int l,int r,int o,int L,int R,int vis)
{
if(L<=l&&r<=R)
{
if(vis==1){
f[o]=f[o]*2%mod;
tree[o]=2*tree[o]%mod;
}
else {
ff[o]=ff[o]*2%mod;
treef[o]=2*treef[o]%mod;
}
return;
}
pushdown(o);
int m=l+r>>1;
if(L<=m)insert1(lson,L,R,vis);
if(m>1;
ll ans=0;
if(L<=m)ans=(ans+query(lson,L,R,vis))%mod;
if(m>1;
if(p<=m)update(lson,p,x);
else update(rson,p,x);
pushup(o);
}
bool cmp(node a,node b)
{
if(a.a==b.a)return a.b