【10.24 牛客普及（四）】 卡片 题解

题目

$Alice$和$Bob$各带来一个正多边形卡片。
$Alice$的卡片是边长为$A$的正$M$边形，$Bob$的卡片是边长为$B$的正$N$边形。
$Alice$和$Bob$将两张卡片摆放在一起，其中两张卡片并不重叠，并且有至少一个公共顶点和一条公共边。
$Alice$喜欢旋转，因此她沿$Bob$的卡片顺时针旋转自己的多边形。
旋转的中心点是多边形公共边上一点，且旋转过程中两张卡片不重叠。
$Alice$想知道，在旋转多少次过后，$Alice$的正多边形会回到原位置。

---

输入

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

---

输出

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

---

样例

input 1
2 4 3 4

output 1
8

explain
前两次操作如下：

input 2
3 4 4 4

output 2
24

input 3
2020 1024 2021 1025

output 3
828200

---

数据范围

对于10%的数据，$M$=$N$=4，且$A$≤$B$≤10；
对于另外30%的数据，$M$≤1000，$N$≤1000，且$A$≤$B$≤1000；
对于另外30%的数据，$B$是$A$的倍数；
对于100%的数据，1≤$A$≤B≤10⁶，3≤$M$≤10⁶,3≤$N$≤10⁶。

---

解题思路

先求出使$A$卡片和$B$卡片能有一个顶点重合一回
要走多少条边
操作多少次
然后求要走的边数和$B$卡片的边数的最小公倍数
最小公倍数除以要走的边数
得出一共要走多少回
与操作数相乘
即为结果

---

代码

#include<iostream>
#include<cstdio>
using namespace std;
long long a,n,b,m,cz,bs=1,x,y;
long long gcd(long long x,long long y)
{ 
	if (x%y==0)
	   return y;
	   else return gcd(y,x%y);
}
long long lcm(long long a,long long b)
{ 
	return a*b/gcd(a,b);
}
int main()
{
	scanf("%lld%lld%lld%lld",&a,&n,&b,&m);
	x=b;
	y=x%a;
	if (y)
	   cz=x/a+1;
	   else cz=x/a;  //第一条边预处理
	while (y)  //还未有顶点重合
	{
		  bs++;  //要走的边数
		  x=b-a+y;  //上一次多走的，这次不用走
		  y=x%a; 
		  if (y)
		     cz+=x/a+2;
		     else cz+=x/a+1;  //转角还要多+1
	} 
	m=lcm(bs,m);  //求要走多少会
	printf("%lld",cz*(m/bs));
	return 0;
}

本文地址：https://blog.csdn.net/qq_45621109/article/details/109271082