結果

問題 No.551 夏休みの思い出（２）
コンテスト
ユーザー tossy
提出日時 2017-08-12 10:37:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 49 ms / 4,000 ms
コード長 2,274 bytes
コンパイル時間 1,569 ms
コンパイル使用メモリ 170,328 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-13 04:45:41
合計ジャッジ時間 4,612 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1120000000

long mod_pow(long x, long n, long p){
  if(x==0) return 0;
  long res=1;
  x %= p;
  while(n>0){
    if(n&1) res=res*x%p;
    x=x*x%p;
    n>>=1;
  }
  return res;
}
long mod_inv(long x, long p){ return mod_pow(x%p, p-2, p); }

// Cipolla's algorithm (modulous p should be a prime)
// calculate a : a^2 = x mod p
long mod_sqrt(long x, long p){
  x%=p;
  if(x==0) return 0;
  if(p==2) return x;
  auto is_square = [&](long a){ return mod_pow(a, (p-1)/2, p) == 1; };
  if(!is_square(x)) return -1;
  long y = 2;
  while(is_square((y*y-x+p)%p)) y++;
  long r = (y*y-x+p)%p;
  auto mul = [&](pair<long,long> u, pair<long,long> v){
    long s = (u.fi*v.fi + u.se*v.se%p*r)%p;
    long t = (u.se*v.fi + u.fi*v.se)%p;
    return mp(s,t);
  };
  long e = (p+1)/2;
  auto ret = mp(1LL,0LL);
  auto v = mp(y, 1LL);
  while(e>0){
    if(e&1) ret = mul(ret, v);
    v = mul(v, v);
    e /=2;
  }
  return ret.fi;
}

int main(){
  long p,r,q;
  cin>>p>>r>>q;

  rep(_,q){
    long a,b,c;
    cin>>a>>b>>c;
    long d = b*b-4*a*c;
    d%=p;
    if(d<0) d+=p;
    long rt = mod_sqrt(d, p);
    if(rt==-1) cout << -1 << endl;
    else if(rt==0){
      long x = -b * mod_inv(2*a, p);
      x %= p;
      if(x<0) x += p;
      cout << x << endl;
    }
    else {
      long aa = mod_inv(2*a, p);
      long x = (-b+rt)*aa %p;
      long y = (-b-rt)*aa %p;
      if(x<0) x+=p;
      if(y<0) y+=p;
      if(x>y) swap(x,y);
      cout << x << " " << y << endl;
    }
  }

  return 0;
}
0