Quadratic equation

Posted on | In , , ,

题目链接

题意

已知$b,c$,计算，满足

思路

所以这题主要就让你解一个。
二次剩余模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
const ll mo = 1e9 + 7;
const ll mod = mo;
ll ksm(ll k,ll n)
{
    ll s=1;
    for(;n;n>>=1,k=k*k%mo) if(n&1) s=s*k%mo;
    return s;
}
 
namespace number
{
    ll D;
    struct Z
    {
        ll x,y;
        Z(ll _x=0,ll _y=0){x=_x,y=_y;}
    };
    Z operator +(const Z &x,const Z &y) {return Z((x.x+y.x)%mo,(x.y+y.y)%mo);}
    Z operator -(const Z &x,const Z &y) {return Z((x.x-y.x+mo)%mo,(x.y-y.y+mo)%mo);}
    Z operator *(const Z &x,const Z &y) {return Z((x.x*y.x%mo+D*x.y%mo*y.y%mo+mo)%mo,(x.y*y.x%mo+x.x*y.y%mo)%mo);}
    Z opt(const Z &x) {return Z(mo-x.x,mo-x.y);}
    Z pwr(Z k,ll n)
    {
        Z s=Z(1,0);
        for(;n;n>>=1,k=k*k) if(n&1) s=s*k;
        return s;
    }
}
using namespace number;//其实这部分像减法，相反数什么的都没什么用...
 
pair<ll,ll> cipolla(ll k)
{
    k%=mo;
    if(ksm(k,(mo-1)/2)==mo-1) return make_pair(-1,-1);
    if(k==0) return make_pair(0,0);
    ll a=rand()%mo;
    while(ksm((a*a%mo-k+mo)%mo,(mo-1)/2)<=1) a=rand()%mo;
    D=(a*a%mo-k+mo)%mo;
    ll v=(pwr(Z(a,1),(mo+1)/2)).x;
    return make_pair(v,mo-v);
}
 
int main()
{
    int T;
    scanf("%d", &T);
    ll inv2 = (mod + 1) / 2;
    while (T--)
    {
        ll b, c;
        scanf("%lld%lld", &b, &c);
        ll tmp = b * b % mod - c * 4 % mod;
        tmp = (tmp + mod) % mod;
        pair<ll, ll> f = cipolla(tmp);
        if (f.first == -1)
        {
            puts("-1 -1");
            continue;
        }
        ll xsuby = f.first;
        ll x = (b + xsuby) % mod * inv2 % mod;
        ll y = (b - x + mod) % mod;
        if (x > y)
            swap(x, y);
        printf("%lld %lld\n", x, y);
    }
    return 0;
}

0%