今天上午是钟皓曦老师的讲授,下午是吴耀轩老师出的题给我们NOIP模拟考了一下下(悲催暴零)

今天的内容——数论

话说我们可能真的是交了冤枉钱了,和上次清明培训的时候的课件及内容一样(哭。

五一培训 清北学堂 DAY4-LMLPHP

整除性

五一培训 清北学堂 DAY4-LMLPHP

五一培训 清北学堂 DAY4-LMLPHP

质数的性质:

五一培训 清北学堂 DAY4-LMLPHP

√n判质数:

按照素数的定义:我们枚举从2到√n,若其中没有一个数是n的因子,则说明n是个质数!

证明为什么到√n:

若n有因数,则n可以写成a*b的形式,我们假设a<=b,若两个数都大于√n,则乘起来一定大于n呀,所以一定有个大于等于√n,一个小于等于√n,证毕!

所以说我们就有了一个直接暴力判质数的方法qwq,时间复杂度O(√n)。

但是太慢了,判一个或几个数还是可以的,若是判一个大范围内的所以质数,那就要GG了。

nlogn判质数(我也不知道叫啥,就这么叫吧):

我们来想一个问题:如果一个数是质数,那么它的倍数是不是质数?

显然不是!因为的它的倍数都有该质因子!

所以这个算法的思路就是:如果我们现在在判断一个数n是否为质数,在判完后我们可以将所求范围内所有它的倍数标记为“不是质数”。

实际代码也就三行,简单明了qwq,时间复杂度O(nlogn):

#include<iostream>
#include<cstdio>
using namespace std;
int not_prime[]; //存1~n是否为质数
int main()
{
int n;
cin>>n;
for(int i=;i<=n;i++)
for(int j=i+i;j<=n;j+=i) //将i的所有倍数标记为不是质数
not_prime[j]=true;
for(int i=;i<=n;i++)
if(not_prime[i]==false) cout<<i<<endl;
return ;
}

埃拉斯特尼筛法(埃氏筛):

这个筛法就是上面那个筛法的改进版,我们只将质数的所有倍数标记为不是质数就行了,这样就可以减少一部分数被重复标记。

证明:若我们将合数的倍数也判为不是质数,根据唯一分解定理:所有的合数都能写成几个质数乘积的形式,也就是说,这个合数已经被比他还小的质因子筛过了,就不用重复再筛一次了。

调和级数:

五一培训 清北学堂 DAY4-LMLPHP

代码很简单,就是在上面判断一下是否为质数就好了:

#include<iostream>
#include<cstdio>
using namespace std;
int not_prime[]; //存1~n是否为质数
int main()
{
int n;
cin>>n;
for(int i=;i<=n;i++)
for(int j=i+i;j<=n;j+=i) //将i的所有倍数标记为合数
if(not_prime[i]==false) //保证只将质数的倍数筛掉
not_prime[j]=true;
for(int i=;i<=n;i++)
if(not_prime[i]==false) cout<<i<<endl;
return ;
}

时间复杂度:O(nlog logn)——已经很快了,很接近线性筛

欧拉筛(线性筛)

这个是埃氏筛的再改进版qwq,真强啊!

虽然埃氏筛已经保证大部分的数不被重复筛,但是还有那一小部分呀!

什么?你不信!

你看:

6这个数,它的质因子有2和3,按照埃氏筛的算法,它还是会被2和3标记一次,谁让它俩都是质数呢。

埃拉斯特尼:tql,这我都没想到%%%

那又咋办呢?

欧拉筛!!!

它的思路是:保证每个数只被它的最小质因数筛掉,这样的话每个数就只被筛了一次,时间复杂度是O(n);

五一培训 清北学堂 DAY4-LMLPHP

五一培训 清北学堂 DAY4-LMLPHP

线性筛能处理积性函数!而其他筛法不能!

五一培训 清北学堂 DAY4-LMLPHP

五一培训 清北学堂 DAY4-LMLPHP

五一培训 清北学堂 DAY4-LMLPHP

超级简单的代码:

#include<iostream>
#include<cstdio>
using namespace std;
int gcd(int a,int b) //求两个点的最大公约数
{
if(b==) return a; //0和任何数的最大公约数都是这个数
return gcd(b,a%b); //辗转相除法
}
int main()
{
int a,b;
cin>>a>>b;
cout<<gcd(a,b)<<endl;
return ;
}

C++内自带的求最大公因数的函数:

__gcd(注意两个下划线)

若gcd(a,b)=d,则一定可以写出ax+by=d,且有多组解

所以我们要求一组x和y的值,咋办呢?

扩展欧几里得算法!exgcd,求不定方程!

五一培训 清北学堂 DAY4-LMLPHP

五一培训 清北学堂 DAY4-LMLPHP

五一培训 清北学堂 DAY4-LMLPHP

五一培训 清北学堂 DAY4-LMLPHP

模意义下的的除法

要用到费马小定理:

如果p是一个质数,而整数a不是p的倍数,则有a^(p-1)≡1(mod p)。

五一培训 清北学堂 DAY4-LMLPHP

P是质数

那么就可以转化成:

五一培训 清北学堂 DAY4-LMLPHP

五一培训 清北学堂 DAY4-LMLPHP

以上亮眼操作是限制于P是质数以上的,难道P不是质数就GG了?

NONONO!!!

有个叫欧拉定理的东东!

五一培训 清北学堂 DAY4-LMLPHP

五一培训 清北学堂 DAY4-LMLPHP

五一培训 清北学堂 DAY4-LMLPHP

五一培训 清北学堂 DAY4-LMLPHP

2.高精度

我们都知道:

Int 和long long都是有范围的:

五一培训 清北学堂 DAY4-LMLPHP

所以就算是long long,如果数的范围超过了20位,也无济于事,那咋办呢?说好的能计算一切数的!没错,我们用到了高精度!

高精度实际是模拟竖式运算,遵循的原则一样:

各位对其,逐位运算。

怎么实现呢?

假设有一个很大的数,我们用数组来存它的每一位,咋存?

以19260817为例:

很自然很单纯的想法是一位一位的按顺序像这样存进去:

五一培训 清北学堂 DAY4-LMLPHP

但这样就出现了一个问题:运算时各位没有对齐,是按最高位对齐的,显然不行!

那咋办?反过来存!:

五一培训 清北学堂 DAY4-LMLPHP

假设我们又存进去一个123,也反过来存:

五一培训 清北学堂 DAY4-LMLPHP

这样的话,它们的各位就对齐啦qwq,没错就是这么简单!

写代码啦(高进度加法为例):

A+B Problem

刚学OI几天的萌新的代码:

五一培训 清北学堂 DAY4-LMLPHP

Zhx:只要改两步就AC!

1.将你的高精度模板贴过来(为什么感觉不大对劲呢);

2.将int a,b;  改成gaojing a,b;(gaojing是结构体)

结构体中有一个专门的初始化的函数——构造函数

#include<iostream>
#include<cstdlib>
#include<cstring> using namespace std; struct gaojing
{
int z[];
int l; gaojing() //构造函数
{
l=;
memset(z,,sizeof(z)); //清空
} friend istream& operator>>(istream &cin, gaojing &a) //一个我永远也不会懂的读入流
{
static char s[];
cin >> s;
int l=strlen(s); //先以字符串的形式读入,方便计算位数
for (int i=;i<l;i++)
a.z[i] = s[l-i-] - ''; //转化为int类型的,并倒着存进去
a.l = l; //记录长度 return cin; //zhx说一定要写return cin(表示不懂qwq)
} friend ostream& operator<<(ostream &cout,const gaojing &a) //输出流
{
for (int i=a.l-;i>=;i--)
cout << a.z[i]; return cout;
}
}; gaojing operator+(const gaojing &a,const gaojing &b) //重点,高精算法的核心,这里用了一下重载运算符,能进入函数的就是前面定义的两个gaojing类型的数
{
gaojing c; //作为答案 int l = max(a.l,b.l); //算出答案可能的长度
for (int i=;i<l;i++)
{
c.z[i] += a.z[i] + b.z[i];
c.z[i+] += c.z[i] / ; //进位
c.z[i] = c.z[i] % ;
}
if (c.z[l] != ) l++; //处理运算后増位的情况
c.l = l; return c;
} gaojing operator*(const gaojing &a,const gaojing &b) //高精度乘法,也是重载运算符,只不过重载*号
{
gaojing c; for (int i=;i<a.l;i++)
for (int j=;j<b.l;j++)
c.z[i+j] += a.z[i] * b.z[j]; //普通模拟竖式运算 c.l = a.l+b.l; //计算答案可能的位数
for (int i=;i<c.l;i++)
{
c.z[i+] += c.z[i] / ; //进位
c.z[i] = c.z[i] % ;
}
while (c.l> && c.z[c.l]==) //去除前导零
c.l--;
c.l ++; return c;
} int main()
{
gaojing a,b;
cin >> a >> b;
a+b;
cout << a*b << endl;
}

3.进制转换

二进制以10为例:

五一培训 清北学堂 DAY4-LMLPHP

第一个问题:

将一个十进制的x转化成一个k进制的数

用短除法!!!

例如我们将55转化成一个三进制的数:

五一培训 清北学堂 DAY4-LMLPHP

然后将所有得到的余数从下往上写:

就得到了答案: 2001(3进制)

注意一个小细节:2001不能读作两千零一(因为这默认是十进制),只能读作二零零一

第二个问题:

将一个k进制的数转化成一个十进制的数

我们可以将这个数写成一个k位的数(因为是k进制):

五一培训 清北学堂 DAY4-LMLPHP

那么转化后的十进制就是:

五一培训 清北学堂 DAY4-LMLPHP

不理解?举个例子!

将一个三进制的2001转化成十进制:

五一培训 清北学堂 DAY4-LMLPHP

常用的一些进制:

二进制,八进制,十进制,十六进制

如果你不想定义一个十进制的数,你就可以在它前面加一个0(表示二进制),例如:

Int a=1001     实际a为1001

Int a=01001    实际a为9

五一培训 清北学堂 DAY4-LMLPHP

十六进制中要用x乘来表示计算十六进制;

十六进制每一位的取值是0~15,那么我们用字母来表示10~15:

A—10

B—11

C—12

D—13

E—14

F—15

……………………考试的下午qwq(爆零)……………………

好难呀,一题都不会qwq,老师讲了之后还是只会思路~

五一培训 清北学堂 DAY4-LMLPHP

这个题一看就是LCA模板吧(再说上面都写了),考试的时候真后悔没有把他搞懂qwq,不过现在懂啦!

再看一下LCA的原理及实现:

五一培训 清北学堂 DAY4-LMLPHP

五一培训 清北学堂 DAY4-LMLPHP

五一培训 清北学堂 DAY4-LMLPHP

但是这样好像很慢,尤其是len层数特别大的时候,那怎么呢?我们在用倍增法:

五一培训 清北学堂 DAY4-LMLPHP

这个实际上是用了二分的思想吧,说下思路:

第一步和之前一样,也是将x和y跳到同一层上;

然后我们用一个grand[x][i]数组来表示编号为x的结点向上跳了2^i层后的结点编号,那么grand[x][0]就是x的父亲结点对吧(因为2^0是1,那么意思就是x向上跳了一层)

那么对于一般的结点,都有grand[x][i]=grand[grand[x][i-1]][i-1]

正常学生:这……跨度有点大吧!

没错,这确实跨度有点大,老师刚开始就这么讲还不仔细解释一番,听不懂怪我喽!

但是,既然你都已经看过来了,我肯定会仔细滴讲给你听啦:

先考虑一下这个问题:2^i=2^(i-1+1)=2^[(i-1)+1]=2^(i-1)*2=2^(i-1)+2^(i-1)      别说你看不懂这个,这不是初中学的嘛?

换句话说,你直接往上跳2^i层和先跳2^(i-1)层再跳2^(i-1)层是一样的

那么我们分别将两种方式表达出来,它们是相等的:

直接跳2^i层: grand[x][i]

分两步跳: 跳完一次后,此时所在的结点是grand[x][i-1],没错吧;接下来把那一坨式子看做一个整体,如果整体感差的话你可以换元换成a

那么第二次跳后所在的结点就是:grand[a][i-1],把a换过去就是grand[ grand[x][i-1] ][i-1](换个颜色更直观)

两个式子做等号,就是上面的式子:grand[x][i]=grand[grand[x][i-1]][i-1]

有木有感觉突然明白啦?什么,没有。。。。好吧我收回刚才的话qwq

水一发洛谷LCA模板题解:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=;
int head[*maxn],to[*maxn],next[*maxn],grand[*maxn][],dep[maxn]; //注意开两倍大小的数组,因为这个图是无向图
//head[i]是存以i结点为起点的最后一条出边的编号
//to[i]数组是存第i条边的终点
//next[i]是存以i结点为起点的所有出边中的倒数第二条出边的编号,其实也就是head[i]的上一条边
int n,m,s,edge_sum=; //edge_sum记录边数
void add(int x,int y) //用链式前向星(链表)建图
{
next[++edge_sum]=head[x]; //根据我们定义的head与next的含义得出
head[x]=edge_sum; //有新的边加入,则将head[x]内的值更新
to[edge_sum]=y; //当前边的终点是y
}
void dfs(int v,int deep)
{
dep[v]=deep; //记录v结点的深度
for(int i=head[v];i>;i=next[i]) //后序访问v的所有出边
{
int u=to[i]; //u记录当前边的终点,也就是说u是v的儿子
if(!dep[u]) dfs(u,deep+),grand[u][]=v; //如果该儿子u的深度没被更新,则更新它,并记录u的父亲是v
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y); //我们让x是深度最大的那个
for(int i=;i>=;i--)
if(dep[y]<=dep[x]-(<<i)) x=grand[x][i]; //让x和y跳到同一层上
if(x==y) return y; //如果跳到同一点上了,说明这个点就是最近公共祖先
for(int i=;i>=;i--) //倍增找最近公共祖先
{
if(grand[x][i]!=grand[y][i]) //如果跳不到公共祖先,那就往上跳
{
x=grand[x][i]; //将x和y往上跳
y=grand[y][i];
}
}
return grand[x][]; //因为我们只要求跳不到同一点就往上跳,所以这样操作之后它们再往上跳一层也就是它们的最近公共祖先了
}
int read() //快读
{
char ch=getchar();
int a=;
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<='')
{
a=a*+(ch-'');
ch=getchar();
}
return a;
}
int main()
{
memset(head,,sizeof(head)); //head数组初始化,好像可以去掉
n=read(),m=read(),s=read(); //这个题数据那么大,快读优化下
for(int i=;i<n;i++) //n-1条边
{
int x=read(),y=read();
add(x,y); //题目中给的是无向图,所以也要反过来建一次
add(y,x);
}
grand[s][]=s; //设起点s的父亲就是自己
dfs(s,); //从深度为1的起点开始深搜
for(int i=;(<<i)<=n;i++) //利用状态转移方程计算出每个点的grand值
for(int j=;j<=n;j++)
grand[j][i]=grand[grand[j][i-]][i-];
for(int i=;i<=m;i++) //m次询问
{
int x=read(),y=read();
printf("%d\n",lca(x,y));
}
return ;
}

这道题看来ok了?NO!

这道题实际是数学题qwq(大雾~

来,我们一步步分析:

首先这是一颗满k叉树,那么它满足这个性质:对于任何一个结点(除叶结点)它的儿子都有k个!

我们求这个树里任意两个结点的最近公共祖先的深度,如果只按每个结点对树的贡献来说,那么这个问题就转化成了任意两个结点有多少个公共祖先!

以我的想法解释一下(不一定对哈,助于理解嘛):

你想想,我们找到了结点a和b的最近公共祖先c了,我们现在要求它的深度,那么如果c的上面还有父亲的话,假设为d,那么d一定是a和b的公共祖先(没有最近),这样的话是不是c的深度就要+1了?

如果d上面还有父亲,那么c又被往下顶了一层,深度又+1……这样看来:这个最近公共祖先c上面有多少个祖先,c的深度就加几,再加上c这个结点,合起来不就是求有多少个公共祖先嘛?

五一培训 清北学堂 DAY4-LMLPHP

a和b有一个公共祖先,所以最近公共祖先的深度为1;

五一培训 清北学堂 DAY4-LMLPHP

此时c还有父亲,那么c的深度+1,a和b有两个公共祖先,所以c的深度为2;

往下各位读者自己脑补脑补就好啦!

我们还可以再将问题进行转化:

我们已经要求对于任何结点a和b有多少个公共祖先了,那么我们将问题反过来:求任意一个点看看它是多少对结点的公共祖先!

但是这样暴力好像一定会TLE,我们可以做下优化:

五一培训 清北学堂 DAY4-LMLPHP

这样以来,对于每一层的所有结点,我们只有找一个结点看看它是多少对结点的公共祖先就好了。

五一培训 清北学堂 DAY4-LMLPHP

对于上面的化简,配合等比数列求和公式效果更佳哦!

五一培训 清北学堂 DAY4-LMLPHP

有同学对于∑那一块一脸懵逼,没关系,给你解释一下:

我们要求的答案是每个点看看是多少对结点的公共祖先,然后求和,所以我们要遍历每一层的结点,当然每一层只要找一个就好啦!

所以这个∑从1遍历到n,这是所有的层数,然后我们随便找个结点,利用上面的公式,那么这一层上任意一个点都有五一培训 清北学堂 DAY4-LMLPHP个符合要求的,这一层一共有K^(i-1)个点(这是满叉树的性质),所以要乘上它;

但这只是60分的做法(以本蒟蒻的水平理解到这一步已经很不容易了,接下的满分做法直接gg)!!

还是一个问题:太慢!!!

这是满分做法,也需要些数学功底嘛,所以我才说是一道数学题qwq:

五一培训 清北学堂 DAY4-LMLPHP

附上满分代码:

#include <bits/stdc++.h>

using namespace std;

const int mod = ;
typedef long long LL;
int fpm(int p, int k)
{
int res = ;
for (p %= mod; k; k >>= , p = (LL) p * p % mod)
if (k & ) res = (LL) res * p % mod;
return res;
}
int main()
{
freopen("lca.in", "r", stdin);
freopen("lca.out", "w", stdout);
int n, K; cin >> n >> K;
int e = fpm(K - , mod - ); //(K - 1) ^ (-1)
int x = (fpm(K, n) - ) * (LL) e % mod; //(K ^ n - 1) / (K - 1)
int ans = (fpm(K, n + ) + ) * (LL) x % mod;
ans = (ans - * n * (LL) fpm(K, n)) % mod;
ans = ans * (LL) e % mod * (LL) e % mod;
cout << (ans < ? ans + mod : ans);
}

 

05-11 22:55