#196490 (C++14) No.551 夏休みの思い出（２）

提出ソース

結果

問題	No.551 夏休みの思い出（２）
ユーザー	tossy
提出日時	2017-08-12 10:37:32
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	52 ms / 4,000 ms
コード長	2,274 bytes
コンパイル時間	1,619 ms
コンパイル使用メモリ	166,660 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-04-21 06:09:34
合計ジャッジ時間	4,887 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	3 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	4 ms 5,376 KB
testcase_04	AC	7 ms 5,376 KB
testcase_05	AC	12 ms 5,376 KB
testcase_06	AC	17 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	3 ms 5,376 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	2 ms 5,376 KB
testcase_26	AC	2 ms 5,376 KB
testcase_27	AC	48 ms 5,376 KB
testcase_28	AC	48 ms 5,376 KB
testcase_29	AC	43 ms 5,376 KB
testcase_30	AC	47 ms 5,376 KB
testcase_31	AC	44 ms 5,376 KB
testcase_32	AC	48 ms 5,376 KB
testcase_33	AC	47 ms 5,376 KB
testcase_34	AC	46 ms 5,376 KB
testcase_35	AC	45 ms 5,376 KB
testcase_36	AC	45 ms 5,376 KB
testcase_37	AC	52 ms 5,376 KB
testcase_38	AC	52 ms 5,376 KB
testcase_39	AC	49 ms 5,376 KB
testcase_40	AC	51 ms 5,376 KB
testcase_41	AC	48 ms 5,376 KB
testcase_42	AC	50 ms 5,376 KB
testcase_43	AC	48 ms 5,376 KB
testcase_44	AC	48 ms 5,376 KB
testcase_45	AC	48 ms 5,376 KB
testcase_46	AC	51 ms 5,376 KB
testcase_47	AC	2 ms 5,376 KB
testcase_48	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード