题解 P6322 【[COCI2006-2007#4] PRSTENI】

· · 题解

传动比（类似）

设有两个圆环，半径分别是x，y；

第一个圆环转1圈，转动距离是它的周长，即2πx；

第二个圆环的周长是2πy，第一个圆环带动它转动的圈数为2πx/2πy；

化简得x/y，当然要约分。设约分后形式是a/b；

从第二个齿轮开始，转动的距离=齿轮周长*转动圈数，即(a/b)2πx，下一个齿轮周长仍为2πy，化简得下一个齿轮转动圈数为(a/b)x/y，也要约分；

需要注意的是这里的所有数值都要实时更新。

证毕。

#include<iostream>
#include<cstdio>
using namespace std;
int gcd(int x,int y)
{
    if(x%y==0)return y;
    return gcd(y,x%y);
}//传统的辗转相除法
int main()
{
    int n,x,y,k;cin>>n>>x>>y;
    int a=x/gcd(x,y),b=y/gcd(x,y);
    printf("%d/%d\n",a,b);//可以先处理两组
    for(int i=3;i<=n;i++)
    {
        scanf("%d",&k);x=y,y=k;
        int p=(a*x/b)/gcd(a*x/b,y),g=y/gcd(a*x/b,y);
        printf("%d/%d\n",p,g);
        a=p,b=g;
    }//数据要实时更新
    return 0;
}

思路不难，代码易懂。