The thirth day in Changle.
在长乐的第十三天
今天开始讲数学基础,矩阵快速幂和质数与约数。
又是只会打模版的一天。
每日贴题
题目
本题运行时错误,找不出来。
代码如下:
#include<bits/stdc++.h>
using namespace std;
int L,R,p[10000100],v[10000100],cnt;
void init(int n){
memset(v,1,sizeof v);
cnt=0;
v[1]=0;
for(int i=2;i<=n;i++)
{
if(v[i])
{
p[++cnt]=i;
}
for(int j=2;i*p[j]<=n;j++)
{
v[p[j]*i]=0;
if(i%p[j]==0)
{
break;
}
}
}
return;
}
int main(){
if(cin>>L>>R)
{
init(50000);
memset(v,1,sizeof v);
for(int i=0;i<cnt;i++)
{
int pri=p[i];
for(int j=max(2*pri,(L+pri-1)/pri*pri);j<=R;j+=pri)
v[j-L]=0;
}
cnt=0;
for(int i=0;i<=R-L;i++)
{
if(v[i]&&i+L>1) p[cnt++]=i+L;
}
if(cnt<2)cout<<"There are no adjacent primes.";
else{
int minn=0,maxn=0;
for(int i=0;i+1<cnt;i++){
if(p[i+1]-p[i]>p[maxn+1]-p[maxn]) maxn=i;
if(p[i+1]-p[i]<p[minn+1]-p[minn]) minn=i;
}
printf("%d,%d are closest, %d,%d are most distant.\n",p[minn],p[minn+1],p[maxn],p[maxn+1]);
}
}
return 0;
}
ps.明天讲同余问题(隔壁数竞的),信息竞赛逐渐数学化。。。。。。
由费马小定理,欧几里得算法,欧拉定理为主力军的初等数论将于明日来袭。
在线无语。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
还有三天就可以回家了QAQ。