五指山

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 983 字

在长度为n的圆圈上，每次逆时针走d，从x到y

一本通
练习

正文

/*
原题：「一本通 6.4 练习 2」五指山（NEFU 84）
题意：在长度为 n 的圆圈上，每次逆时针走 d，从 x 到 y，求最少翻的次数。
思路：翻 k 次后位置 (x + k·d) mod n ≡ y，即 d·k ≡ (y-x) (mod n)；用扩展欧几里得求该线性同余的最小非负解，无解则 Impossible。
复杂度：每组 O(log n)。
易错点：k 取最小非负解需对 (n/g) 取模归一化；负数余数要加模；gcd(d,n) 不整除 (y-x) 时输出 Impossible。
*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;y=0;
        return a;
    }
    ll x1,y1;
    ll g=exgcd(b,a%b,x1,y1);
    x=y1;
    y=x1-(a/b)*y1;
    return g;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    if(!(cin>>T))return 0;
    while(T--){
        ll n,d,x,y;
        cin>>n>>d>>x>>y;
        // d·k ≡ (y-x) (mod n)
        ll b=(y-x)%n;
        if(b<0)b+=n;
        ll k,u;
        ll g=exgcd(d,n,k,u);
        if(b%g!=0){
            cout<<"Impossible\n";
            continue;
        }
        ll ng=n/g;
        k=((k%ng)+ng)%ng;
        k=(__int128)k*(b/g)%ng;
        cout<<k<<'\n';
    }
    return 0;
}

五指山

正文

一本通·提高篇的其它内容