集训 2020.2.29
数论复习--(gcd)
gcd 的两种写法
(gcd(a,b)=gcd(b,a\%b)=gcd(a-b,b))
扩展gcd
找出一对整数((x,y))使得(ax+by=gcd(a,b))
证明过程如下：
令(ax+by=gcd(a,b)=d),有(b'x+(amod b)y'=d)
变成了求(bx'+(amod b)y'=d)
然后再把这个式子递归下去，因为我们知道递归下去肯定会出现(b=0)的情况，此时我 们是可以求出(x’)和(y’)的，之后再不断代回去，就能够求出一组解了。
不能理解也没关系，代码会背就好了！
背代码！
//1
void exgcd(int a,int b,int &x,int &y){
if(!b){
x=1;y=0;return;
}
exgcd(b,a%b,x,y);
int temp;
temp=x;
x=y;
y=temp-(a/b)*y;
return ;
}
//2 紫书上的，更短更好背，也更容易让人迷糊
void exgcd2(int a,int b,int &x,int &y){
if(!b){
x=1;y=0;return ;
}
exgcd(b,a%b,y,x);
y-=(a/b)*x;
return ;
}
求出通解
为了求出更多的解，我们有：
前两个式子移项得到：
这个式子除以(d)得到：
显然(a',b')互质，因此(x_1-x_2=kb',y_2-y_1=ka',kin Z)
因此我们得到了：(x_2=x_1-kb',y_2=y_1+ka',kin Z)
求出(x)作为最小正整数的解
用公式：(x=(x\%b+b)mod b)
更一般的问题
更一般地，求解(ax+by=c)的问题
裴蜀定理：(ax+by=c)有解，当且仅当(gcd(a,b)|c),即(c=kgcd(a,b),kin Z)
方程两边除以(k)得到：$$aleft( dfrac{x}{k}
ight)+bleft( dfrac{y}{k}
ight)=gcd(a,b)$$
还元得到：(ax_1+by_1=gcd(a,b))
显然能够求出(x_1,y_1)，因此也能求出原来的解
例题讲解
1 LGP1082 同余方程
求关于(x)的同余方程(axequiv 1(mod b))的最小正整数解。
题解
把这个同余式子转换一下就是(ax\%b=1),换句话说就是(by+1=ax(y=dfrac{a}{b}))
移项之后得到(ax+by=1)（这样写的话(y)肯定就是负数了）
然后就用(operatorname{exgcd})即可。
2 LGP1516 青蛙的约会
纬线上有两只青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方 向，单位长度(1)米，这样我们就得到了一条 首尾相接的数轴。设青蛙A的出发点坐标是 (x)，青蛙B的出发点坐标是(y)。青蛙A一次能跳(m)米，青蛙B一次能跳(n)米，两只青蛙跳 一次所花费的时间相同。纬度线总长(L)米。
现在要你求出它们跳了几次以后才会碰面。有可能永远碰不上。
其中(0<x
eq yle 2000000000,0<m,n<2000000000,0<Lle 210000000)
题解
设(x_0)为最终结果，让青蛙相对运动，可列出式子：((m - n)x_0 =y-x(mod L))
显然该式可以转化为：((m - n)x_0 + Ly_0 = y - x)
再变换一下变成：(ax + by = c)
变成了熟悉的(operatorname{exgcd})问题，正常求解即可。
3 CF527A Playing with Paper
一张纸长(a)，宽(b)。每次我们切下来最大的正方形然后扔掉，直到剩下的纸也为正方 形即停。求剪出的正方形个数。
题解
本题答案是更相减损次数的个数，用辗转相除优化之
！！！
4 LGP5436 【XR-2】缘分
求不超过(n)的两个正整数的最小公倍数最大是多少.
(nle 10^9)
题解
不难知道(n)与(n-1)是互质的，显然没有比它俩还大的(operatorname{lcm})了，于是答案为(n(n-1))
(n=1)不要忘了讨论了。还有(operatorname{long long})
5 LGP5535 【XR-3】小道消息
有(n)个人，其中第(i)个人的衣服上有一个数(i+1)，小X发现了一个规律：当一个衣服上的数为 (i) 的人在某一天知道了一条信息，他会在第二天把这条信息告诉衣服上的数为 (j)的人，其中$ gcd(i,j)=1$（即 (i,j)的最大公约数为 (1)）。在第 0 天，小 X 把一条小道消息告诉了第 (k) 个人，小 X想知道第几天时所有人都会知道这条小道消息。
可以证明，一定存在所有人都知道了这条小道消息的那一天。
提示：你可能需要用到的定理——伯特兰-切比雪夫定理。
(2 le n le 10^{14})
(1 le k le n)
有关伯特兰—切比雪夫定理
伯特兰—切比雪夫定理说明：若整数(n > 3)，则至少存在一个质数(p)，符合(n < p < 2n − 2)。
另一个稍弱说法是：对于所有大于(1)的整数(n)，至少存在一个质数(p)，符合(n < p < 2n)。
其中两个加强结果(定理)：
定理 1： 对任意自然数(n > 6)， 至少存在一个(4k + 1)型和一个(4k + 3)型素数 (p) 使得(n < p < 2n)。
定理 2： 对任意自然数(k)， 存在自然数(N)， 对任意自然数 (n > N)至少存在(k) 个素数(p)使得 (n < p < 2n)。
题解
- 答案只可能是1或2
- 当(k+1)是质数的时候
如果到(n+1)为止没有(k+1)的倍数时，显然答案为1
如果有倍数的话，答案就是2，感性理解很显然，证明也不难，(2(k+1))一定与(2(k+1)-1) 互质 - 当(k+1)不是质数的时候
由那个奇怪的定理可知，一定存在一个质数(p)在(dfrac{n}{2})和(n)之间，显然(k+1)不可能是(p)的倍 数（(2p>n)），因此第一步先拿到p，然后 再由p传播到所有人
6 POJ2142：The Balanc
有一天平和两种数量无限的砝码（重为(a)和(b)），天平左右都可以放砝码，称质量为(c) 的物品，要求：
放置的砝码数量尽量少；
当砝码数量相同时,总质量尽量小。
7 POJ2115：C Looooops
for(i=A;i!=B;i+=C){i%=1<< k;}
问：会循环多少次（有可能死循环）
8 JSK43512
https://nanti.jisuanke.com/t/43512
给出(n)个相邻酒桶在坐标轴的位置，要求通过移动一些酒桶，使得每个酒桶之间的距离为(k)。
求最小移动距离
（另外这题评测机跑的飞快，你可以认为 1s 1e8）
(1le N,Kle 10^6)
题解
我们设原始位置为 (x)，第一个啤酒摊位置为(a)，将其排序。某一油桶(i)位置是(x_i)，它移动的距离是位置与它本来应该在的位置(a+k(i-1))的差值，我们可以得到：
通过移项，得到：
通过预处理(c_i=x_i-k(i-1))，式子变形成为：
则转化到了：数轴上存在(c_i)的点，寻找一个点a使得ans最小，根据定理可知，a为c的中位数时ans有最小值。
定理：给定数轴上的(n)个点，求一个到他们的距离之和尽量小的点。
结论是：这个点是这(n)个数的中位数。所以只需排序即可。严谨的证明如下：
在数轴上标出这(n)个点，假定数轴上标好了六个点，从左到右编号(C_i(iin {1,2,3,4,5,6}))，如果选定(C_4,C_5)之间的一点( ext P)，之后把这个点向左（或者向右，效果相同，假定向左）(D)个单位长度，则( ext P′)到它左边的四个点距离减少了(4D)，到右边的两个点距离增加了(2D)，总的来说距离减小了(2D)。
通过这样的移动，发现在奇数个数构成的数列，满足条件的数是最中间的数，而偶数个数构成的数列是最中间两个数的平均数，得证。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
const int N=1e6+7;
ll n,k;
ll arr[N],c[N];
int main()
{
scanf("%lld %lld",&n,&k);
for(int i = 1;i <= n;i ++){
scanf("%lld",&arr[i]);
}
sort(arr+1,arr+1+n);
for(int i = 1;i <= n;i ++) c[i] = arr[i] - k*(i-1);
sort(c+1,c+1+n);
ll ans = c[(1+n)/2];
if(n%2==0) ans = (c[n/2]+c[n/2+1])/2;
ll sum = 0;
for(int i = 1;i <= n;i ++){
sum += abs(ans-c[i]);
}
printf("%lld",sum);
return 0;
}
// by whh