今天上了一些“幼儿园数学”，在吴老师的帮助下，勉强理解部分，在此写下博客，怕今后遗忘，也可以供一些仍然不太理解的同学参考。（可能会有理解方面的错误，感谢指出）。

1.拓展欧几里得

这种算法求解ax+by=c这一类的问题，条件是(a,b)|c，否则无解，证明PPT上介绍的十分详细，但是我们27中讲解这个是用了一种比吴老师更简洁的代码：

int exgcd(int a,int b,int &x,int &y){

if (b==0){x=1;y=0;return a;}

r=exgcd(b,a%b,x,y);

int t=x;x=y;y=t-a/b*y;

return r;

}

例题：小凯的疑惑

当时我有这样一种疑问，就是为什么取u = (b - 1); b = -1 或u = -1; v = (a - 1) 都可以，吴老师给我的解答是：

不可能同时有两个正数解，u变大，v就要变小；v变大，u就要变小，所以不可能满足。

2.逆元

“在模意义下，也有除以一个数等于乘上它的逆元。”

宋老师跟我讲过：这个东西还蛮重要的，务必要掌握。那什么是逆元呢？

ax≡1(mod b),且 a与b互质，那么我们就能定义: x为a的逆元，记为a^-1(不会打指数233333333)。

那么上面那个式子可以转化为：

ax-by=1

因为在模意义下，正负号不管,所以得到：

ax+by=1

这不就可以用拓展欧几里得算出x吗？

因为x是正整数，所以用x=(x+b)%b取到正数。

而阶乘算法和线性算法我记得一篇题解上证明的非常好，不需要我解释，给出地址：https://www.luogu.org/problemnew/solution/P3811

这个网址上的第一篇题解介绍逆元的线性和阶乘算法十分详细。

3.缩系

定义不要我说了，计做欧拉函数φ（n）。

φ（n）是积性函数

如何求也不要我说了，PPT上解释的详细，要代码的私信。

欧拉定理

不想描述了，给出证明：

例题：上帝与集合的正确用法

题解吴老师给了一份比较标准的，在这里给一份我写的注释代码： include

using namespace std;

typedef long long ll;

ll t,x;

ll phi(ll n){//求n的欧拉函数值

ll e=n;

for (ll p=2; p*p<=n; p++)

if (n%p==0){

while (n%p==0)

n/=p;

e=e/p*(p-1);

}

if (n>1)

e=e/n*(n-1);

return e;

}

ll pow(ll a,ll b,ll n){//快速幂

ll sum=1;

while (b){

if (b%2==1) sum=sum*a%n;

a=a*a%n;

b/=2;

}

return sum;

}

ll pow2(ll a,ll b){//两个快速幂

ll sum=1;

while (b){

if (b%2==1) sum=sum*a;

a=a*a;

b/=2;

}

return sum;

}

ll work(ll k){

if (k==1) return 0;//当你取模的那个数为1时，结果一定为0

ll p=0;

while (k%2==0){//分解成2^k*q

k/=2;

p++;

}

ll phi_k=phi(k);

ll ans=work(phi_k);//无限个2模q

(ans+=(phi_k-p%phi_k))%=phi_k;//减k模那个

ans=pow(2,ans,k)%k;//（上面的指数已经求好了），快速幂一下

return ans*pow2(2,p);//把外面的2^k乘

}

int main(){

scanf ("%lld",&t);

while (t--){

scanf ("%lld",&x);

printf ("%lld\n",work(x));

}

return 0;

}

4.中国剩余定理（线性同余方程组）

这个只要记一下，证明上课吴老师讲的时候没有及时记录，抱歉。

例题：屠龙勇士

这个是真的没有听懂，毕竟我一年还没学到。。。

总之，我还是存在一些问题的，谢谢大家指出。