题意给定\(p,x\)，求满足\(a^2+b^2\equivx\pmodp\)的解的组数，保证\(p\)为若干奇素数的乘积且\(\mu(p)\not=0\)。\(n\le10^5,p\le10^7\)。前置知识二次剩余综合题。首先二次剩余有一个重要的符号勒让德符号：\(\left(\dfrac{a}{p}\right)\)，这个东西在当\(a\)在模\(......

线性同余方程组基本问题是求解形如下面的线性同余方程组\[\begin{aligned}\begin{cases}x\equiva_1\pmod{p_1}\\x\equiva_2\pmod{p_2}\\...\\x\equiva_n\pmod{p_n}\end{cases}\end{aligned}\]在\(\operatorname{OI}\)中有广泛的应用......

同余关系在基本概念的部分中，我们已经简单了解了整除与余数而在这一个部分中，我们将更复杂的了解余数中的同余关系由于本节内容多在模意义下讨论，故文中可能会出现一些\(=,\equiv\)混用的情况，见谅此处获取本节调试数据/代码包全文绝大多数内容是对[0]中讲......

[NOIP2012普及组]摆花题目描述小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共mmm盆。通过调查顾客的喜好，小明列出了顾客最喜欢的......

欧几里得算法(exgcd)简介用于求解\(ax+by=gcd(a,b)\)，在求\(gcd\)的过程中进行求解。原理由辗转相除法的过程我们可以得到：\[ax_1+by_1=gcd(a,b)\\bx_2+(a\bmodb)y_2=gcd(b,a\bmodb)\\由欧几里得定理可知：gcd(a,b)=gcd(b,a\bmodb)\\所以ax_1+by_1=bx_2+(a\bmodb)y_2......

前两天老师还让我们狂做紫题，为什么今天就要求我们对这一道蓝题打暴力qwqupdata：今天突然看到，这道题也是紫题了qwqP1081开车旅行这道题一看就是dp一类的题，然后就会很顺畅的想到倍增awa首先，看一下暴力怎么打。这道题是当年的T4，然后有整整70分的暴力分，这是十分可观的awa。所......

对于同余方程的话就是一个经典扩展欧几里得求逆元的题目。这个可以转换成,我们需要求的只是x和k从而得到一组解。通常我们会得到a和b两个元素，假设a是7，b为40，通过扩展欧几里得进行运算。这时也就是，我们第一步先开始从a，b两个数字里找到最大的那个在这里的话是40，然后利用大的......

\(a\equivb\pmodn\Leftrightarrow(a-b)\bmodn=0\Leftrightarrown|(a-b)\)\(a\bmodn<n\)\((a\pmb)\bmodn=((a\bmodn)\pm(b\bmodn))\bmodn\)\((a\cdotb)\bmod=((a\bmodn)\cdot(b\bmodn))\bmodn......

1.模运算基本性质基本概念：若整数\(a,b\)除以\(p\)的余数相等，则称\(a,b\)在模\(p\)意义下同余，记作\(a\equivb\pmod{p}\)或者\(a\bmodp=b\bmodp\)。模运算的定义：\[a\bmodp=\begin{cases}a-p\lfloor\dfrac{a}{p}\rfloor&a\geq0\\-(-a\bmodp)&a<0......

[题解]P1083[NOIP2012提高组]借教室解法\(1\)：线段树-\(O((n+m)\logn)\)比较直观的一种做法，但是可能需要卡一下输入（这里没卡也过了，但要注意输入是\(10^6\)级的，为了保险一定要加）。#include<bits/stdc++.h>#definelc(x<<1)#definerc((x<<1)|1)#defineintlonglong......