| 1234 |
- #include <iostream>
- #include <numeric>
- using namespace std;long long exgcd(long long a,long long b,long long&x,long long&y){if(!b){x=1;y=0;return a;}long long g=exgcd(b,a%b,y,x);y-=a/b*x;return g;}
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;while(T--){long long n,s,k;cin>>n>>s>>k;long long g=gcd(n,k);if(s%g){cout<<-1<<'\n';continue;}n/=g;s/=g;k/=g;long long x,y;exgcd(k,n,x,y);x%=n;if(x<0)x+=n;cout<<((n-s%n)%n*x%n)<<'\n';}}
|
