洛谷noip 模拟赛 day1 T1

时间：2023-03-10 03:32:04
洛谷noip 模拟赛 day1 T1

T7925 剪纸

题目描述

小芳有一张nnn*mmm的长方形纸片。每次小芳将会从这个纸片里面剪去一个最大的正方形纸片，直到全部剪完（剩下一个正方形）为止。

小芳总共能得到多少片正方形纸片？

输入输出格式

输入格式：

一行两个整数nnn和mmm

输出格式：

一行一个整数，总共能得到的纸片数量。

输入输出样例

输入样例#1： 
6 4
输出样例#1： 
3

说明

对于30%的数据满足n=1n=1n=1

对于60%的数据满足n,m≤103n,m\leq 10^{3}n,m≤10​3​​

对于100%的数据满足n,m≤1012n,m \leq 10^{12}n,m≤10​12

存一下代码...........

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

LL read(){

    LL ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

LL n,m,ans;

LL gcd(LL x,LL y){

    while(y){

        LL p=x%y;

        x=y;

        y=p;

    }

    return x;

}

int main()

{

    n=read(); m=read();

    if(n<m) swap(n,m);

    if(m==){printf("%lld\n",n); return ;}

    LL now=gcd(n,m);

    if(now!=) n/=now,m/=now;

    while(n%m!=){

        if(n<m) swap(n,m);

        now=n/m;

        ans+=now;

        n=n-m*now;

    }printf("%lld\n",ans+n/m);

    return ;

}

​​

相关文章