Submission #9233

#TimeUsernameProblemLanguageResultExecution timeMemory
9233kcm1700Quaternion inverse (kriii2_Q)C++14
4 / 4
136 ms1088 KiB
#include <cstdio> #include <algorithm> using namespace std; int mod; pair<long long, long long> extended_gcd(long long a, long long b) { if (b == 0) return make_pair(1, 0); pair<long long, long long> t = extended_gcd(b, a % b); return make_pair(t.second, t.first - t.second * (a / b)); } long long modinverse(long long a, long long m) { return (extended_gcd(a, m).first % m + m) % m; } int main(){ int T; scanf("%d%d",&mod,&T); while(T-->0){ long long a,b,c,d; scanf("%lld%lld%lld%lld",&a,&b,&c,&d); long long tmp = (a*a+b*b+c*c+d*d) % mod; if (tmp == 0) { puts("0 0 0 0"); continue; } tmp = modinverse(tmp, mod); a *= tmp; b *= -tmp; c *= -tmp; d *= -tmp; a %= mod; a += mod; a %= mod; b %= mod; b += mod; b %= mod; c %= mod; c += mod; c %= mod; d %= mod; d += mod; d %= mod; printf("%lld %lld %lld %lld\n", a,b,c,d); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...