站外题,简单数学求助

回复帖子

@andychen_2012  2021-10-14 13:35 回复

有T组测试数据,每组数据给一个整数x。

计算是否存在这样的一个连续整数区间使得这个区间里的数加起来为素数,且这个区间包含整数x。如果存在,输出这个整数区间的最短长度,否则输出-1.

$$1<=T<=10^6$$

$$-10^7<=x<=10^7$$

#include<cstdio>
int T;
bool prime[20000005];
const int M=20000005;
int x;
inline void init(){
    prime[0]=prime[1]=1;
    for(int i=4;i<=M;i+=2)
        prime[i]=1;
    for(int i=3;i<=M;i+=2){
        if(prime[i]) continue;
        for(int j=i+i;j<=M;j+=i)
            prime[j]=1;
    }
}
inline int cal(int n){
    bool f=0;
    int ans=0;
    if(n<0)
        ans=-2*n+1,n=-n+1,f=1;
    //printf("%d %d %d\n",n,ans,n);
    if(!prime[n]) return ans+1;
    if(!prime[n+n-1]||!prime[n+n+1]) return ans+2;
    for(int i=1;;++i){
        if(!prime[n+i])
            return f?ans+i+2:2*n+i;
        if(!prime[n+n+i+i+1])
            return f?ans+i+3:2*n+i+1;
    }
    return -1;
}
int main(){
    scanf("%d",&T);
    init();
    while(T--){
        scanf("%d",&x);
        int ans=0;
        if(x==0)
            ans=3;
        else
            ans=cal(x);
        printf("%d\n",ans);
    }
    return 0;
}
@Juzh  2021-10-14 14:38 回复 举报

口胡前缀和思路,一个记录整数,一个记录x个数,(会爆long long 吧)

@54Teddy 2021-10-14 14:54 回复 举报

口胡一个思路好了……

先筛一下到2e7的素数……多一点可能更好

每个询问判一下如果x是素数直接输出1

首先答案不可能是-1……因为直接取一个素数p>|x|,从-p+1加到p肯定包含x而且和为p……这也说明了答案最多是2p-1

考虑连续一段大于一个的正整数的和……从a加到b是$\frac{(a+b)(b-a+1)}{2}$,考虑到a+b>2,如果和是素数,肯定b-a+1=2,a+1=b,然后看一下x的正负。

如果x正:看一下2x+1 or 2x-1是不是素数,是的话直接输出2,不是的话找一下$\geq$2x-1的最小的素数p,和$\geq$x的最小的素数q看一下$\frac{p+1}2$和q哪个小照着前面那个答案不可能是-1的解释乱搞一下答案。

x负除了不可能答案是2以外其实差不多……取个绝对值跟之前就差不多了……得看一下包含之类的

口胡的算法……如果不对轻喷

@54Teddy 2021-10-14 14:56 回复 举报

如果x绝对值比较小的话……比如说什么0,正负1,正负2,正负3之类的最好特判一下……感觉会出问题

@54Teddy 2021-10-14 14:57 回复 举报

关于筛素数……肯定是要筛到大于2e7的第一个素数的……只筛到2e7可能会出问题

@andychen_2012  2021-10-14 21:08 回复 举报

@54Teddy AC了!

十分感谢思路的拓展,对负数做了专门的处理。

改后的代码如下:

        if(-n+1>1)
            if(!prime[-n+1])
                return -2*n+2;
        if(-2*n+3>1)
            if(!prime[-2*n+3])
                return -2*n+3;
        ans=-2*n+1,n=-n+1;
        //printf("%d %d\n",n,ans);
        for(int i=n;;++i){
            if(!prime[i])
                return ans+1;
            if(!prime[i+i+1])
                return ans+2;
            ans+=2;
        }
        return ans;
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。