二次剩余（简：没有证明）

二次剩余用处
有点像逆元，解题的时候模情况下不要出现小数

所需要的就是这个x。一下所说是p为质数的情况。

定理
1.总共有（p - 1）/ 2+1种n使得方程有解。
2

3.
求解代码

#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<map>
#include<stack>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<unordered_map>
#include<string>
#include<cmath>
#include<cstdio>
#include<fstream>
#include<time.h>
#define lson rt<<1
#define rson rt<<1|1
#define fmid (tree[rt].l + tree[rt].r) / 2

using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
const ll mod = 1e9 + 9;
const double eps = 1e-6;
const double PI = acos(-1);
#define MOD(a, b) a >= b ? a % b + b : a
#define random(a,b) (rand()%(b-a+1)+a)
void acc_ios()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
}

ll w;
bool ok;
struct QuadraticField
{
    ll x, y;
    QuadraticField operator*(QuadraticField T)
    {
        QuadraticField ans;
        ans.x = (this->x * T.x % mod + this->y * T.y % mod * w % mod) % mod;
        ans.y = (this->x * T.y % mod + this->y * T.x % mod) % mod;
        return ans;
    }
    QuadraticField operator^(ll b)
    {
        QuadraticField ans;
        QuadraticField a = *this;
        ans.x = 1;
        ans.y = 0;
        while(b)
        {
            if(b & 1)
            {
                ans = ans * a;
                b--;
            }
            b /= 2;
            a = a * a;
        }
        return ans;
    }
};


ll fast_pow(ll a, ll b)
{
    ll res = 1;
    while(b)
    {
        if(b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

ll legender(ll a)
{
    ll ans = fast_pow(a, (mod - 1) / 2);
    if(ans + 1 == mod)
        return -1;
    else
        return ans;
}

ll getW(ll n, ll a)
{
    return ((a * a - n) % mod + mod) % mod;
}

ll solve(ll n)
{
    ll a;
    if(mod == 2)
        return n;
    if(legender(n) == -1)
        ok = false;
    srand((unsigned)time(NULL));
    while(1)
    {
        a = random(0, mod - 1);
        w = getW(n, a);
        if(legender(w) == -1)
            break;
    }
    QuadraticField ans, res;
    res.x = a;
    res.y = 1;
    ans = res^((mod + 1) / 2);
    return ans.x;
}

ll comp(ll a, ll b)
{
    if(a < b) return 0;
    if(a == b) return 1;
    if(b > a - b) b = a - b;
    ll ans = 1, ca = 1, cb = 1;
    for(int i = 0; i < b; i++)
    {
        ca = ca * (a - i) % mod;
        cb = cb * (b - i) % mod;
    }
    ans = ca * fast_pow(cb, mod - 2) % mod;
    return ans;
}


int main()
{
    acc_ios();
    ll n, ans1, ans2;
    cin>>n;
    ok = true;
    n %= mod;
    ans1 = solve(n);
    ans2 = mod - ans1;
    if(!ok)
    {
        cout<<"no root"<<endl;
        return 0;
    }
    if(ans1 == ans2)
        cout<<ans1<<endl;
    else
        cout<<ans1<<" "<<ans2<<endl;
    return 0;
}

本文地址：https://blog.csdn.net/weixin_43891021/article/details/107522209