P2284 [HNOI2003] 密室之门

设当前的密室第 \(i\) 个转盘初始为 \(c_i\)。
\(a,n\) 很小但是场上看不到，考虑枚举两个转盘，设他们为 \(i,j\)，考虑判断祂们是否合法。
容易列出方程 \(\begin{cases}x\equiv c_i\pmod {b_i}\\x\equiv c_j\pmod {b_j}\end{cases}\)，即\(b_i\times k_1-b_j\times k_2=c_j-c_i\) 然后用裴蜀定理秒了。
判断是 \(\mathcal{O}(\log a)\) 的，所以总时间复杂度为 \(\mathcal O(n\times a^2\log a)\)。

代码

/*
Luogu P2284 [HNOI2003] 密室之门
2026-03-12
*/
#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T&x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
        f?x=-x:0;
    }
    template<typename T>
    inline void write(T x){
        if(x==0){putchar('0');return ;}
        x<0?x=-x,putchar('-'):0;short st[50],top=0;
        while(x) st[++top]=x%10,x/=10;
        while(top) putchar(st[top--]+'0');
    }
    inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
    inline void write(char c){putchar(c);}
    inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
    inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
    template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
    template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
    template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
const int maxn=110;
int n,b[maxn],c[maxn];
void solve(){
    read(n);
    for(int i=1;i<=n;i++) read(b[i],c[i]);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){
        int g=__gcd(b[i],b[j]);
        if((c[i]-c[j])%g){write("impossible\n");return ;}
    }
    write("possible\n");
}
signed main(){
    int T;read(T);
    while(T--) solve();
    return 0;
}