本文主要是介绍CF C. Candy Store，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接：Problem - C - Codeforces
题意：多测，先给出n代表n种糖果，每种糖果分别给出数量和单价，可以将糖果平均分成若干袋，每一袋的的价格是一袋糖果数量×单价，对于每一种糖果都求出一袋的价格，对于每种糖果都需要用标签贴出一袋的价格，但是如果相邻的糖果价格相同，那么就可以用一个标签来代表价格，问最少使用几个标签。
思路：如果一段糖果价格是一样的，那么设置价格为cost。因为每一袋糖果的价格都是由数量和单价相乘构成的，所以cost%单价=0，所以cost是这一段单价的最小公倍数。但是知道了价格没有用，还需要考虑真的可以让每一袋的价格都是cost吗？每一种糖果的数量%一袋子糖果的数量=0，这个公式上下同时成单价，那么下面就变成了cost。所以一段糖果可以使用一个标签，那么每种糖果的总价是数量×单价，总价%cost=0，这就意味着，这一段的最小公约数%cost=0。因为cost是单价的最小公倍数，所有如果一段糖果的总价最小公约数%单价的最小公倍数=0，那么就可以使用一个标签来表示这一段糖果。
//冷静，冷静，冷静
//调不出来就重构
//#pragma GCC optimize(2)
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=1000000007;
ll a[N],b[N];
ll lcm(ll x,ll y)
{return x*y/__gcd(x,y);
}
void Jiuyuan()
{ll n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i]>>b[i];ll llcm=b[1],lgcd=a[1]*b[1];ll ans=1;for(int i=2;i<=n;i++){ll va=lcm(llcm,b[i]),vb=__gcd(lgcd,a[i]*b[i]);if(vb%va==0){llcm=va;lgcd=vb;continue;}ans++;llcm=b[i];lgcd=a[i]*b[i];}cout<<ans<<endl;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll T=1;cin>>T;while(T--){Jiuyuan();}return 0;
}这篇关于CF C. Candy Store的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
