题目描述

链接：https://ac.nowcoder.com/acm/contest/7610/C
来源：牛客网
Alice和Bob各带来一个正多边形卡片。
Alice的卡片是边长为A的正M边形，Bob的卡片是边长为B的正N边形。
Alice和Bob将两张卡片摆放在一起，其中两张卡片并不重叠，并且有至少一个公共顶点和一条公共边。
Alice喜欢旋转，因此她沿Bob的卡片顺时针旋转自己的多边形。
旋转的中心点是多边形公共边上一点，且旋转过程中两张卡片不重叠。
Alice想知道，在旋转多少次过后，Alice的正多边形会回到原位置。

输入描述: 

一行，四个整数A,M,B,N，含义如题目描述所述。

输出描述: 

一行，一个数Ans，表示Alice旋转的次数。
示例1

输入 

2 4 3 4

输出 

8

思路与分析

首先可以发现题目中的m是没有意义的
所以问题可以转化为一个点在多边形B上每次前进a

从上图可以看出有两种情况
1.前进边长a一步完成（不经过多边形B的顶点的旋转）
2.前进边长a两步完成（经过多边形B的旋转）
思路：假设不考虑第二种情况下前进的次数+考虑第二种情况多旋转的（也就是计算共经过多少次多边形B的顶点）
先计算第一种情况： 总路程 多边形B的周长：b*n和边长a的最小公倍数（差不多就是一个点在一个圆上每次循环移动a重新回到原点）  su(总次数)=总路程/多边形A的边长
第二种情况多旋转的：lcm(a,b)是一个周期，以第一个样例为例，看下图吧，不好解释，x=lcm（a，b）/a
为在这个周期内移动的次数，y=lcm（a，b）为在这个周期内的路程等于y条矩阵B的边长，所以这个周期内有y-1个顶点，所以多旋转的次数为 总次数=su/x（共多少个周期）*（y-1）（顶点数）

AC代码 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll gcd(ll a,ll b)
{
    return a%b==0?b:gcd(b,a%b);
}
ll lcm(ll a,ll b)//求最小公倍数
{
    return a*b/gcd(a,b);
}
int main()
{
    ll a,m,b,n;
    scanf("%lld%lld%lld%lld",&a,&m,&b,&n);//su表示要移动的总次数
    ll su=lcm(a,b*n)/a,y=lcm(a,b)/a,x=lcm(a,b)/b;//y表示移动lcm(a,b)前进y次
    printf("%lld\n",su+su/y*(x-1));            //x表示移动lcm(a,b)，经过了x条b边
    return 0;
}