atcoder046C - AtCoDeer and Election Report
程序员文章站
2022-07-14 10:34:15
...
题目:C - AtCoDeer and Election Report C-AtCoDeer
题意很明显,每次给出一个比例,要求两个数在不能减少的基础上,以为最小的变化形成这个比例.
思路:让上一次的 x,y:x/y=n*(a/b) (a,b就是题目中的T和A),这里需要求的是n最小能取多少。可以选择从1开始枚举直到n * a>=x&&n * b>=y但是这样做时间复杂度太高了,而且没必要.可以让n=max(x/a,y/b),再判断一下n * a与x大小,n * b与y的大小.
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
int main()
{
ll n,t,x=1,y=1;//x,y不为0
cin>>t;
while(t--)
{
ll a,b;
cin>>a>>b;
n=max(x/a,y/b);
while(n*a<x||n*b<y)n++;
x=a*n,y=b*n;
}
cout<<x+y<<"\n";
return 0;
}