@poorpool 2017-10-05T20:07:21.000000Z 字数 4199 阅读 1184

清北学堂金秋营 day5

%%%zrt

题解

T1

先排个序。
能拼出[0,x]，现在最小的是k。要是k>x+1，岂不是x+1拼不出来。
考虑前缀和+1与下一个元素的关系。

T2

（默默地打表找规律23333）
答案的数量级是 $\ O(\sqrt{n})$ 级别的。

30：直接枚举。
60：

for(int i=1; i<=n; i++){
    int a=n/i;
    int b=n/a;
    i = b;
    //a偏小，则b偏大。
    //blablabla
}

100：
分成几部分来看。
第一部分是除以不同的i得到不同的解；
第二部分是除以不同的i的得到有重复的解，且他们连续。
二分第一个满足n/i-n/(i+1)<=1（实数除）

T3

直接搜是2^30复杂度太高。
分两半搜，变成2*2^15。
搜出2^15个三元组。
按照钻石数、钱数排序而分类。
又搜出另一半的2^15个三元组。
后来的三元组，每个三元组都对前面的三元组有一个严格要求（钻石数）。因此，后面的每个三元组，与前面三元组结合必定为一个区间（因为你排的序）。可用前缀和预处理前面的三元组。

数论

快速幂

int ksm(int a,int b,int p）{
    if(!b)return 1%p;
    int c=pow(a,b/2,p);
    c=c*c%p;
    if(b%1)c=c*a%p;
    return c;
}
//or
int ksm(int a, int b, int c){
    int ret=1%p;
    while(b){
        if(b&1)ret=ret*a%p;
        b>>=1;
        a=a*a%p;
    }
    return ret;
    //2^n=2^(2^0+2^1+2^2...(二进制分解))
}

noip 转圈游戏

素数

$\ O(\sqrt{n})$ 判断素数。
~~学miller-rabin~~

唯一分解定理

筛素数

O(nlogn)埃拉托斯特尼筛
O(n)线性筛（欧拉筛）

for(int i=2; i<=n; i++){
    if(!mindiv[i]/*最小素因子*/){
        mindiv[i] = i;
        prime[++tot] = i;
    }
    for(int j=1; prime[j]*i<=n; j++){
        mindiv[prime[j]*i] = prime[j];
        if(prime[j]!=mindiv[i]) break;
    }
}
//or
for(int i=2;i<=listsize;i++){
    if(isprime[i])prime[++primesize]=i;
        for(int j=1;j<=primesize&&i*prime[j]<=listsize;j++){
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0)break;
        }
}

gcd and lcm

(a, b)==gcd(a, b)
辗转相减：(a, b)=(a, a-b)(a>b)

x|a,x|b ---> x|(ap+bq)

进化即辗转相除：

int gcd(int a, int b){
    return !b?a:gcd(b, a%b);
}

复杂度log级

lcm(a, b) = a/gcd(a, b)*b
事实上
a=p1^a1 * p2^a2 * ...
b=p1^b1 * p2^b2 * ...
(a, b) = p1^min(a1, b1) * p2^min(a2, b2) * ...
[a, b] = p1^max(a1, b1) * p2^max(a2, b2) * ...

费马小定理

if p is a prime,then

$\ a^{p-1}≡1(mod\ p）$

证明

一、准备知识：
引理1．剩余系定理2
若a,b,c为任意3个整数,m为正整数,且(m,c)=1,则当ac≡bc(modm)时,有a≡b(modm)
证明：ac≡bc(mod m)可得ac–bc≡0(mod m)可得(a-b)c≡0(mod m)因为(m,c)=1即m,c互质,c可以约去,a–b≡0(mod m)可得a≡b(mod m)
引理2．剩余系定理5
若m为整数且m>1,a1,a2,a[3],a[4],…a[m]为m个整数,若在这m个数中任取2个整数对m不同余,则这m个整数对m构成完全剩余系.
证明：构造m的完全剩余系（0,1,2,…m-1）,所有的整数必然这些整数中的1个对模m同余.取r1=0,r2=1,r[3]=2,r[4]=3,…r=i-1,1
引理3．剩余系定理7
设m是一个整数,且m>1,b是一个整数且(m,b)=1.如果a1,a2,a3,a4,…am是模m的一个完全剩余系,则ba1,ba2,ba[3],ba[4],…ba[m]也构成模m的一个完全剩余系.
证明：若存在2个整数ba[i]和ba[j]同余即ba[i]≡ba[j](mod m),根据引理2则有a[i]≡a[j](mod m).根据完全剩余系的定义和引理4（完全剩余系中任意2个数之间不同余,易证明）可知这是不可能的,因此不存在2个整数ba和ba[j]同余.由引理5可知ba1,ba2,ba[3],ba[4],…ba[m]构成模m的一个完全剩余系.
引理4．同余定理6
如果a,b,c,d是四个整数,且a≡b(mod m),c≡d(mod m),则有ac≡bd(mod m)
证明：由题设得ac≡bc(mod m),bc≡bd(mod m),由模运算的传递性可得ac≡bc(mod m)
二、证明过程：
构造素数p的完全剩余系P={1,2,3,4…(p-1)},因为(a,p)=1,由引理3可得A={a,2a,3a,4a,…(p-1)a}也是p的一个完全剩余系.令W=1*2*3*4…*(p-1),显然W≡W(mod p).令Y=a*2a*3a*4a*…(p-1)a,因为{a,2a,3a,4a,…(p-1)a}是p的完全剩余系,由引理2以及引理4可得a*2a*3a*…(p-1)a≡1*2*3*…(p-1)(mod p)即W*a^(p-1)≡W(modp).易知(W,p)=1,由引理1可知a^(p-1)≡1(modp）

逆元

先处理n!逆元。
$\ n^{-1}=n!^{-1}*(n-1)!$
$\ n!^{-1}*n=(n-1)!^{-1}$

裴蜀定理

if a,b is int,(a,b)=d,对任意x,y as int,ax+by为d倍数。特别的，一定存在x，y使得ax+by=d成立

扩展欧几里得

初始时有x=1,y=0
每次把b,a%b的xy变成a，b的xy
x*b+y*(a%b)=(b,a%b)=xb+y(a- $\ \lfloor \frac{a}{b}\rfloor$ *b)=ya+(x- $\ \lfloor \frac{a}{b}\rfloor$ *y)b
x'a+y'b=gcd(a,b)
即x'=y,y'=x-a/b

int ExGCD(int a, int b, int& x, int& y)  
{  
    if(b == 0)  
    {  
        x = 1, y = 0;  
        return a;  
    }  
    int d = ExGCD(b, a%b, x, y);  
    int temp = x;  
    x = y;  
    y = temp - a/b*y;  
    return d;  
}

noip2012 同余方程

求ax=1(mod b)
保证有解

即ax+by=1
因为保证有解，所以(a, b)|1(证明：要是gcd！=1，那左边就是整数乘整数必！=1)

ax+by=1，则a(x+b)+b(y-a)=1
（加了一个ab减了一个ab）

解同余思想

欲求ax+by=c
先求ax+by=(a, b)=gcd
同乘c/gcd，得出
ax+by=c的一组解，再得出
a(x+b/gcd)+b(y-a/gcd)=c
（为什么是b/gcd，a/gcd呢？这样可以最大程度把区间长度比解数缩小，从而做到“最小整数解”）

中国剩余定理（CRT）

解同余方程组

有：
x % p1 = a1
x % p2 = a2
x % p3 = a3
...
x % pn = an
各p互素

令m=p1p2p3...pn
构造出
//ni(k,p)是k在模p意义下逆元
x = (m/p1*ni(m/p1, p1)*a1 + ...) c% m

x + k1*p1 = a1
x + k2*p2 = a2
联立（上下相减）
k1p1-k2p2 = a1-a2

欧拉定理

剩余系

模一个数字得到的结果即为一个剩余系。
{1,2,...p-1}（不考虑0）
12：{1,2,3...12}

简化剩余系

只拿出和p 互素的
12：{1,5,7,11}

定理

如果(a, m)=1,a^phi(m)=1(mod m)
$\ a^{\phi(m)} \equiv 1(mod\ m)$

如果(a,b)=1
$\ \phi(ab)=\phi(a)\phi(b)$
如果p为素数
$\ \phi(p^k)=p^k-p^{k-1}=(p-1)p^{k-1}$

pick定理

格点多边形公式：
S=a+b/2-1
其中a表示多边形内部的点数，b表示多边形边界上的点数，s表示多边形的面积。
poj2954

如果两格点横距a纵距b，则再走a/x，b/x（x|a,x|b）到下一格点，即欲使最优，则x=(a, b)

矩阵乘法

在这里我们谈方的。

int a[][]
int b[][]
int c[][]
for(int i=1; i<=n; i++)
    for(int j=1; j<=n; j++)
        for(int k=1; k<=n; k++)
            c[i][j]+=a[i][k]*b[k][j];

f[1~n]
if f[i]*k -> f`[j]
then a[i][j] = k

有结合律无交换律。

考虑斐波那契数列，fib[i]=fib[i-1]+fib[i-2]
f1=fib[k] f2=fib[k+1]
f'1=fib[k+1] f`2=fib[k+2]
（笔者是沙茶啥也不会）

分治乘法

?????

组合数学

lucas定理

c[n][m]%p=c[n%p][m%p]*c[n/p][m/p]%p

一些题目

poj1006 biorhythms

x % [p1, p2]=
(k - x) % 23 = 0
(k - y) % 28 = 0;

余数之和

求x%1+x%2+x%3+...+x%n
范围10^12

即x-x/1*1+x-x/2*2+x-x/3*3+...+x-x/n*n=nx-...-(x/i * i+x/(i+1) * i+1+x/(i+2) * (i+2)-...= nx-...-(x/i)(i+i+1+i+2...)-...
（这啥？？？）