题解：AT_pakencamp_2024_day1_d Coprime Shortest Path

Calamity_Link · 2026-05-14 15:50:20 · 题解

Upd

5.14 初稿。

思路

若 S 与 T 互素，直接一步即可到达。

否则，因为任何正整数与 1 互素，因此先从 S 走到 1，再从 1 走到 T，一共 2 步。

注意要开 long long。

AC Code

#include<bits/stdc++.h>
using namespace std;
long long N,S,T;
int main(){
    cin>>N>>S>>T;
    if(gcd(S,T)==1)
        cout<<1;
    else
        cout<<2;
    return 0;
}