聚龙外国语DAY3

morning
1.整除关系
a|b 表示b mod a=0
若a|b且a|c，则a|(bx+cy)
最大公约数GCD(a,b) 辗转相除
最小公倍数LCM(a,b)
GCD(a,b)LCM(a,b)=ab
2.同余关系
a≡b(mod m)
a-b能被某个自然数m整除
或者理解为a mod m=b mod m
3.同余关系的性质
若a≡b(mod m)
a+c ≡b+c(mod m)
ac ≡bc(mod m)
𝑎𝑎𝑐𝑐 ≡ 𝑏𝑏𝑐𝑐(mod m)
一般的
如果a≡b(mod m)，x≡y(mod m)，则a+x≡b+y(mod m) 如果a≡b(mod m)，x≡y(mod m)，则ax≡by(mod m)
若a mod p=x且a mod q=x,p和q互质，则a mod(pq)=x
如果ac≡bc(mod m)，且c和m互质，则a≡b(mod m)
4.辗转相除
若b=0那么x=1,y=0;
否则
考虑 ax+by=gcd(a,b）与 bx’+(a mod b) y’=gcd(a,b)解的关系
bx’+(a-b*(a/b))y’=gcd(a,b) 这里的除法为整除
ay’+b(x’-(a/b)y’)=gcd(a,b)
所以 x=y’ y=x’-(a/b)y’
就这样迭代下去就可以得出ax+by=gcd(a,b) 的一组解 要变换其他的解只需要
x+kb,y-ka即可
5.逆元
求0<=x<b的x满足 ax=1 (mod b)
gcd(a,b)=1
这样的x我们称为在mod b意义下的a的逆元
求法： 扩展欧几里得
6.费马小定理
费马小定理 ap-1%p=1
证明？
ap-2 即为 a 关于 p 的逆元
（所以似乎以上的东西某位姓张的高一老师好像讲过了来着）
afternooon（0+0+40+0）
T1 chicken
不小心挂了，到现在都不知道怎么RE的
T2 duck
没看懂（），一道奇妙的讨论问题
T3 dog
我居然有分！暴力拿了40（让我来纪念一下我提高的历史新高）

#include<bits/stdc++.h>
using namespace std;
struct fac{
    int color,number,id;
}dog[400005];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        dog[i].color=dog[i].number=dog[i].id=0;
        dog[i].id=i;
        scanf("%d %d",&dog[i].color,&dog[i].number);
        if(i==1) continue;
        if(dog[i-dog[i].number-1].color==dog[i].color)
        {
            int s=i-dog[i].number;
            for(int j=i+1;j>=s;j--)
            {
                dog[j].color=dog[j-1].color;
                dog[j].number=dog[j-1].number;
                dog[j].id=dog[j-1].id;
            }
            dog[i-dog[i+1].number].color=dog[i+1].color;
            dog[i-dog[i+1].number].number=dog[i+1].number;
            dog[i-dog[i+1].number].id=dog[i+1].id;
            //cout<<"no"<<endl;
            //continue;
        }
        else{
        for(int j=i-dog[i].number;j<i;j++)
        {
            if(dog[j].color==dog[i].color)
            {
                for(int k=i+1;k>j;k--)
                {
                    dog[k].color=dog[k-1].color;
                    dog[k].number=dog[k-1].number;
                    dog[k].id=dog[k-1].id;
                }
                dog[j].color=dog[i+1].color;
                dog[j].number=dog[i+1].number;
                dog[j].id=i;
                break;
            }
        }
        }
//      for(int j=1;j<=i;j++) printf("%d ",dog[j].id);
//      cout<<"\n";
    }
    for(int i=1;i<=n;i++) printf("%d ",dog[i].id);
    return 0;
}

T4 合作
我记得好像打过（），来不及打了不管了

（普及组干了260，T1太水了）
（关于我T1A之后找到了让代码挂的数据这件事）