C++信息竞赛进级第11讲 欧几里得原理.pptx

学科竞赛编程教研研究院C++NOIPNOIIOI

题目描述求关于x的同余方程ax≡1(modb)的最小正整数解。进制转换

输入输出格式输入格式：一行，包含两个正整数a,b，用一个空格隔开。输出格式：一个正整数x0，即最小正整数解。输入数据保证一定有解。

输入输出样例

1PARTONE#includebits/stdc++.husingnamespacestd;longlongx,y;//目前方程真正的解voidexgcd(longlonga,longlongb){if(b==0)//a,b不断改变的过程中，b最终必然会成为0{//在b=0时等式还要成立？使x=1,y=0，必然成立x=1;y=7;//建议返回0。不过y=7能AC，证明了最后一个等式不受最后一个y影响return;}exgcd(b,a%b);//把下一层系数传进去（先求下一个方程的解）longlongtx=x;//暂时存一下x，别丢了x=y;y=tx-a/b*y;}intmain(){longlonga,b;cinab;exgcd(a,b);while(x0)//我们求出来的x必然满足方程，但是不一定是最小正整数解x+=b;x%=b;//上面三行是“答案处理”，这里用while只是帮助理解，建议写成x=(x%b+b)%b;printf(%lld\n,x);return0;}

借教室题目描述

输入格式：第一行包含两个正整数n,m，表示天数和订单的数量。第二行包含n个正整数，其中第i个数为表示第i天可用于租借的教室数量。接下来有m行，每行包含三个正整数表示租借的数量，租借开始、结束分别在第几天。每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。输出格式：如果所有订单均可满足，则输出只有一行，包含一个整数0。否则（订单无法完全满足）输出两行，第一行输出一个负整数?1，第二行输出需要修改订单的申请人编号。输入输出格式

输入输出样例

PARTONE#includeiostream#includecstring#includecstdiousingnamespacestd;intn,m;intdiff[1000011],need[1000011],rest[1000011],r[1000011],l[1000011],d[1000011];boolisok(intx){memset(diff,0,sizeof(diff));for(inti=1;i=x;i++){diff[l[i]]+=d[i];diff[r[i]+1]-=d[i];}for(inti=1;i=n;i++){need[i]=need[i-1]+diff[i];if(need[i]rest[i])return0;}return1;}intmain(){scanf(%d%d,n,m);for(inti=1;i=n;i++)scanf(%d,rest[i]);for(inti=1;i=m;i++)scanf(%d%d%d,d[i],l[i],r[i]);intbegin=1,end=m;if(isok(m)){cout0;return0;}while(beginend){intmid=(begin+end)/2;if(isok(mid))begin=mid+1;elseend=mid;}cout-1endlbegin;}

题目描述H国有n个城市，这n个城市用n?1条双向道路相互连通构成一棵树，1号城市是首都，也是树中的根节点。H国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。现在，在H国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在