题解：P12048 [USTCPC 2025] 多边形转动

Needma · 2025-04-06 14:16:43 · 题解

思路分析：首先发现这个题和 m 一点关系没有，接下来思考一段把总时间分成许多整除的时间，即：

int x=b/__gcd(a,b);//x表示转x次整除b

注意到每转 x 次会经历 x+a \times x\div b-1 次操作。然后再算出用多少个这样的整除时间可以回到原点，求最大公因数即可。

ac code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,m1,m2,b,ans; 
signed main(){
    cin>>a>>m1>>b>>m2;
    int x=b/__gcd(a,b); 
    int bian=a*x/b;
    int k=m2/__gcd(bian,m2);
    cout<<k*(x+bian-1);
    return 0;
}