题解 [ABC186E] Throne

cjh20090318 · 2024-01-19 23:43:42 · 题解

同余方程板子题，没过的可以先去看看。

题意

翻译给的很清楚。

分析

看到这个转圈圈的就很容易想到同余方程。

为了方便处理，我们就将编号全部减 1，于是编号就变成 0 \sim N-1。

然后就可以很容易的列出同余方程：

移项可得：

将右边加上 N 使得右边非负：

然后直接求解 x 即可。

代码

//the code is from chenjh
#include<cstdio>
using namespace std;
typedef long long LL;
LL x,y;
LL exgcd(const LL&a,const LL&b){//扩展欧几里得求解同余方程。
    if(!b){
        x=1,y=0;
        return a;
    }
    LL d=exgcd(b,a%b);
    LL z=x;
    x=y;
    y=z-y*(a/b);
    return d;
}
int mian(){
    LL a,b,s;//a 指的是 K，b 指的是 N。
    scanf("%lld%lld%lld",&b,&s,&a);
    LL g=exgcd(a,b),t=(b-s)%b;
    if(t%g) puts("-1");//判断无解的情况。
    else printf("%lld\n",(x%b+b)%b*(t/g)%(b/g));
    return 0;
}
int main(){
    int T;scanf("%d",&T);
    while(T--) mian();
    return 0;
}