Title:
have
no
no
n kinds of candy, among which
i
i
i have
a
[
i
]
a[i]
a[i] pieces, the price of one piece is
b
[
i
]
b[i]
b[i], now it is necessary to bag each candy, assuming that the first
i
i
i kind of pretend
d
[
i
]
d[i]
d[i] pieces per bag, so it must be guaranteed
d
[
i
]
∣
a
[
i
]
d[i]|a[i]
For d[i]∣a[i], the unit price of each bag
c
[
i
]
c[i]
c[i] is the sum of prices
b
[
i
]
x
d
[
i
]
b[i]\times d[i]
b[i]×d[i]. Now put them in bags and place them in the order of the original candies. If the price of a section of bagged candies is the same, then they can be marked with one price tag. How many price tags are needed at least to mark all the bagged candies?
Solution:
assume a paragraph
[
l
,
r
]
[l,r]
[l,r] have the same price, i.e.:
c
[
l
]
=
c
[
l
+
1
]
=
.
.
.
=
c
[
r
?
1
]
=
c
[
r
]
=
b
[
l
]
x
d
[
l
]
=
.
.
.
=
b
[
r
]
x
d
[
r
]
c[l]=c[l + 1]=…=c[r-1]=c[r]=b[l]\times d[l]=…=b[r]\times d [r]
c[l]=c[l + 1]=…=c[r?1]=c[r]=b[l]×d[l]=…=b[r]×d[r ]
remember
c
o
the s
t
=
c
[
l
]
=
.
.
.
=
c
[
r
]
cost=c[l]=…=c[r]
cost=c[l]=…=c[r]
then each
b
[
i
]
,
i
∈
[
l
,
r
]
b[i],i\in[l,r]
b[i], i∈[l,r] are both
c
o
the s
t
cost
The factor of cost, then there is
l
c
m
(
b
[
l
]
,
b
[
l
+
1
]
,
.
.
.
,
b
[
r
?
1
]
,
b
[
r
]
)
∣
c
o
the s
t
lcm(b[l],b[l + 1],…,b[r-1],b[r])|cost
lcm(b[l],b[l + 1],…,b[r?1],b[r])∣cost
at the same time need
d
[
i
]
∣
a
[
i
]
d[i]|a[i]
d[i]∣a[i], then there are
d
[
i
]
∣
a
[
i
]
?
(
b
[
i
]
x
d
[
i
]
)
∣
(
a
[
i
]
x
b
[
i
]
)
,
i
∈
[
l
,
r
]
d[i]|a[i]\Rightarrow (b[i]\times d[i])|(a[i]\times b[i]),i\in[l,r]
d[i]∣a[i]?(b[i]×d[i])∣(a[i]×b[i]),i∈[l,r]
Right now
c
o
the s
t
∣
(
a
[
i
]
x
b
[
i
]
)
,
i
∈
[
l
,
r
]
cost|(a[i]\times b[i]),i\in[l,r]
cost∣(a[i]×b[i]), i∈[l,r]
Right now
c
o
the s
t
cost
cost if all
a
[
i
]
x
b
[
i
]
,
i
∈
[
l
,
r
]
a[i]\times b[i],i\in[l,r]
The factor of a[i]×b[i],i∈[l,r], namely
c
o
the s
t
∣
g
c
d
(
a
[
l
]
x
b
[
l
]
,
.
.
.
.
,
a
[
r
]
x
b
[
r
]
)
cost|gcd(a[l]\times b[l],….,a[r]\times b[r])
cost∣gcd(a[l]×b[l],….,a[r]×b[r])
to be satisfied
(
2
)
(
4
)
(2)(4)
(2)(4) Items with two conditions can be placed in a group, to meet
(
2
)
(
4
)
(2)(4)
(2)(4), only need
l
c
m
(
b
[
l
]
,
b
[
l
+
1
]
,
.
.
.
,
b
[
r
?
1
]
,
b
[
r
]
)
∣
g
c
d
(
a
[
l
]
x
b
[
l
]
,
.
.
.
.
,
a
[
r
]
x
b
[
r
]
)
lcm(b[l],b[l + 1],…,b[r-1],b[r])|gcd(a[l]\times b[l],….,a [r]\times b[r])
lcm(b[l],b[l + 1],…,b[r?1],b[r])∣gcd(a[l]×b[l],….,a[ r]×b[r])
It must be the best result to greedily form a group with the previous product, so only two pointers are needed to find the satisfying
(
2
)
(
4
)
(2)(4)
(2) (4) the number of paragraphs.
#include<iostream>
#include <utility>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <unistd.h>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <set>
#include <map>
#include <stack>
#include <utility>
#include <cctype>
#include <cassert>
#include <thread>
#include <future>
#include <bitset>
#include <thread>
#include <random>
using namespace std;
using ll=long long;
const int N=2e5 + 5,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff, mod=1e9 + 7;
int n,a[N],b[N];
vector<int>c[N];
void solve() {<!-- -->
cin>>n;
for(int i=1;i<=n;i ++ ) {<!-- -->
cin>>a[i]>>b[i];
}
ll ans=1,lcm_val=b[1],gcd_val=1ll*a[1]*b[1];
for(int i=2;i<=n;i ++ ) {<!-- -->
if(gcd(gcd_val,1ll*a[i]*b[i])%lcm(lcm_val,b[i])==0) {<!-- -->
gcd_val=gcd(gcd_val,1ll*a[i]*b[i]);
lcm_val=lcm(lcm_val,b[i]);
} else {<!-- -->
ans + + ;
gcd_val=1ll*a[i]*b[i];
lcm_val=b[i];
}
}
cout<<ans<<endl;
}
int main() {<!-- -->
#ifdef stdjudge
freopen("in.txt", "r", stdin);
auto TimeFlagFirst = clock();
#endif
std::ios::sync_with_stdio(false);
std::cin. tie(nullptr);
int t; cin>>t;
while(t--)solve();
#ifdef stdjudge
freopen("CON", "r", stdin);
std::cout<<std::endl<<"Time-consuming:"<<std::clock()-TimeFlagFirst<<"ms"<<std::endl;
std::cout<<std::flush;
system("pause");
#endif
return 0;
}