CF1766D Lucky Chains
有某位特别爱RE的同学问的老师，由此引发了一场血案
主打的就是一坚持不懈（悲
题意
- 给出两个正整数 $(x,y)$，满足 $(x,y),(x+1,y+1),(x+2,y+2),\dots,(x+k,y+k)$ 都是互质的，直到 $(x+k+1,y+k+1)$ 起不互质
- 问 $k$ 的值，或指出这个互质的序列长度为 $0$ 或是无限长的
其中，$n\leq 10^6, 1\leq x_i < y_i \leq 10^7$
$n$表示测试数量
前置知识
更相减损法
更相减损法：$\gcd(a,b)=\gcd(b,a-b) =\gcd(a,b-a)$
证明：
$$
求证：\gcd(a,b)=\gcd(b,a-b) =\gcd(a,b-a)
\
设d是a,b的因数，那么a=dq_1,b=dq_2
\
也就是：d|a,d|b
\
那么，d|(a-b),d|(b-a)
\
所以，只要d是a,b的因数，该式就恒为真
\
而\gcd(a,b)=d时也满足上述条件，所以\gcd(a,b)=\gcd(b,a-b)=\gcd(a,b-a)
\
证毕
$$
线性筛
可以参考：OI Wiki
先来看看埃氏筛，埃氏筛的思路很简单，就是每找到一个质数，就把他的所有倍数都标记为合数，时间复杂度$O(n\log n)$
但是，埃氏筛有一个很大的问题，就是每一个合数都会被多次标记，这大大增加了算法的时间复杂度
为了解决这个问题，我们就要引入线性筛（又名欧拉筛）
现在，有两个数组，分别存储全部正整数和全部质数，假定现在只出现了$2$:
a = 1, 2
f = 2
当2进入时，和$f$数组中的全部数都相乘，得到一些合数，并标记
2为质数，所以添加到$f$的末尾
接着是3进入
a = 1, 2, 3
f = 2, 3
还是一样，3进入时和$f$数组中的数相乘一遍，排除得到的合数
该$4$进入了：
a = 1, 2, 3, 4
f = 2, 3
和$2,3$一样，$4$也要和$f$中的每一个数相乘，但是由于$4$是合数，所以当他遇到他的质因子$2$时，就要停止了
截至目前，有这么多数已经确定了质数或是合数：
2, 3, 4, 6, 8
那么，我们只需要依此类推，就可以仅用$O(n)$的时间复杂度完成操作
不难发现，当一个合数被标记时，都是以两个数之积的形式被标记的，而其中的最小的质数就是他的最小质因子
可以去打模板练练手
这里给出线性筛的模板代码：
const int Maxn=1e8;
int vis[Maxn+10];
vector<int>a;
void init()
{
vis[1]=1;
for(int i=2;i<=Maxn;i++)
{
if(!vis[i])
{
a.push_back(i);
vis[i]=1;
}
for(int j=0;j<a.size();j++)
{
if(i*a[j]>Maxn) break;
vis[i*a[j]]=1;
if(i%a[j]==0) break;
}
}
}
思路
暴力
很明显，这题给人的第一感觉就是打暴力，枚举$k$，但是瞄一眼数据就知道这个思路是行不通的
更相减损法 优化#1
回到题面，这题的k的表示如下：
$\gcd(a,b)=\gcd(a+1,b+1)=\gcd(a+2,b+2)=......=\gcd(a+k,b+k)=1\而\gcd(a+k+1,b+k+1)\neq 1$
所以这题就是要找一个最大的$k$使得$\gcd(a+k,b+k)=1$
由该式以及更相减损法得到：$\gcd(a+k,b+k)=\gcd(a+k,b+k-(a+k))=\gcd(a+k,b-a)$
所以，想要求出$k$，就无需从头枚举，而是枚举$b-a$即可
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
using namespace std;
int gcd(int x,int y)
{
return y?gcd(y,x%y):x;
}
void run()
{
int x,y;
cin>>x>>y;
if(gcd(x,y)!=1) cout<<0<<endl;
else if(x+1==y) cout<<-1<<endl;
else
{
int g=-1;
for(int i=2;i<=y-x;i++)
{
if((y-x)%i==0)
{
g=i;
break;
}
}
if(g==-1) g=sqrt(y-x);
cout<<(ceil(x*1.0/g))*g-x<<endl;
}
}
signed main()
{
ios::sync_with_stdio(0);
int t;
cin>>t;
while(t--) run();
}
毫无疑问，TLE
线性筛 优化#2
接着，通过观察可以发现：当$k$为合数时，他一定不是最优解，因为合数一定是多个质数之积，如果可以被这个合数整除，那么就一定有更小的质数满足条件
所以可以得出结论：合数解一定不如质数解更优
那么，进一步的优化，就是通过线性筛出所有的质数，每一次只去枚举质数
这次，就可以给时间复杂度再加一个$\log$
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int Maxn=1e7+10;
int a[Maxn];
vector<int>prime;
int gcd(int x,int y)
{
return y?gcd(y,x%y):x;
}
void init()
{
for(int i=2;i*i<=Maxn;i++)
{
for(int j=2;i*j<=Maxn;j++)
{
a[i*j]=1;
}
}
for(int i=2;i<=Maxn;i++)
{
if(!a[i]) prime.push_back(i);
}
}
void run()
{
int x,y;
cin>>x>>y;
if(gcd(x,y)!=1) cout<<0<<endl;
else if(x+1==y) cout<<-1<<endl;
else
{
int m=y-x;
int ans=(ceil(x*1.0/(y-x)))*(y-x)-x;
for(int i=0;prime[i]<=m;i++)
{
if((y-x)%prime[i]==0)
{
ans=min(ans,(int)(ceil(x*1.0/prime[i]))*prime[i]-x);
ans=min(ans,(int)(ceil(x*1.0*((y-x)/prime[i])))*prime[i]-x);
}
}
cout<<ans<<endl;
}
}
signed main()
{
ios::sync_with_stdio(0);
init();
int t;
cin>>t;
while(t--) run();
}
这份代码用的是埃氏筛，当时没有进行关于线性筛的优化，所以TLE了，但是这篇代码如果用了线性筛恐怕依旧会TLE
线性筛性质 优化#3
前面也提到了，埃氏筛中标记一个合数时，一定会有一个数是他的最小质因子，可以将它记录下来
为什么要记录呢？可以发现，如果我们所枚举的质数不是$b-a$的质因子，那么也会浪费很大的时间，所以通过这个小优化，就可以几乎将整体时间复杂度开个方
质因数分解程序如下：（其中f[n]表示$n$的最小因子）
vector<int> factor(int n)
{
vector<int>re;
while(n>1)
{
int x=f[n];
while(n%x==0)
{
n/=x;
}
re.push_back(x);
}
return re;
}
代码
最终，历经千辛万苦，在提交了将近$40$次之后，我终于AC了
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int Maxn=1e7;
int a[Maxn+10];
int f[Maxn+10];
int vis[Maxn+10];
int cnt;
vector<int>prime;
int gcd(int x,int y)
{
return y?gcd(y,x%y):x;
}
void init()
{
vis[1]=1;
for(int i=2;i<=Maxn;i++)
{
if(!vis[i])
{
a[cnt++]=i;
f[i]=i;
vis[i]=1;
}
for(int j=0;j<cnt;j++)
{
if(i*a[j]>Maxn) break;
vis[i*a[j]]=1;
f[i*a[j]]=a[j];
if(i%a[j]==0) break;
}
}
}
vector<int> factor(int n)
{
vector<int>re;
while(n>1)
{
int x=f[n];
if(f[n]==0) x=n;
while(n%x==0)
{
n/=x;
}
re.push_back(x);
}
return re;
}
void run()
{
int x,y;
cin>>x>>y;
if(gcd(x,y)!=1) cout<<0<<endl;
else if(x+1==y) cout<<-1<<endl;
else
{
vector<int>fac=factor(y-x);
int m=fac.size();
int ans=Maxn;
for(int i=0;i<m;i++)
{
// cout<<fac[i]<<endl;
if((y-x)%fac[i]==0)
{
ans=min(ans,(int)(ceil(x*1.0/fac[i]))*fac[i]-x);
// ans=min(ans,(int)(ceil(x*1.0/(m/fac[i])))*(m/fac[i])-x);
// cout<<"> "<<(int)(ceil(x*1.0/fac[i]))*fac[i]-x<<endl;
}
}
cout<<ans<<endl;
}
}
signed main()
{
// freopen("test.in","r",stdin);
ios::sync_with_stdio(0);
init();
int t;
cin>>t;
while(t--) run();
}