@poorpool
2017-10-05T20:07:21.000000Z
字数 4199
阅读 1148
%%%zrt
先排个序。
能拼出[0,x],现在最小的是k。要是k>x+1,岂不是x+1拼不出来。
考虑前缀和+1与下一个元素的关系。
(默默地打表找规律23333)
答案的数量级是级别的。
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(实数除)
直接搜是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 转圈游戏
判断素数。
学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;
}
}
(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
证明
一、准备知识:
引理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!逆元。
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-*b)=ya+(x-*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;
}
求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呢?这样可以最大程度把区间长度比解数缩小,从而做到“最小整数解”)
解同余方程组
有:
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,b)=1
如果p为素数
格点多边形公式:
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]
(笔者是沙茶啥也不会)
?????
推荐《组合数学》
c[n][m]=c[n-1][m]+c[n-1][m-1]
c[n][m]%p=c[n%p][m%p]*c[n/p][m/p]%p
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...)-...
(这啥???)