题解

‮队团加不）ด้้童帅_者仇复

2024-06-16 19:35:37

发布于：广东

49阅读

0回复

0点赞

因为

11/11=1
1001/11=91
100001/11=9091
10000001/11=909091

所以， $\overline{aa}|11,\overline{abba}|11,\overline{abccba}|11,\overline{abcddcba}|11$ ，即偶数位的回文质数只有11.
又因为
$5\le a<b\le100,000,000$
所以不存在9位的回文质数.
说完了，开始暴力！

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> v;
void _init(){
	v.push_back(11);//提前添加11
	for(int i = 1; i <= 9; i += 2){
		int tmp1 = i;
		v.push_back(tmp1);
		for(int j = 0; j <= 9; j++){
			int tmp2 = i * 100 + j * 10 + i;
			v.push_back(tmp2);
			for(int k = 0; k <= 9; k++){
				int tmp3 = i * 10000 + j * 1000 + k * 100 + j * 10 + i;
				v.push_back(tmp3);
				for(int l = 0; l <= 9; l++){
					int tmp4 = i * 1000000 + j * 100000 + k * 10000 + l * 1000 + k * 100 + j * 10 + i;
					v.push_back(tmp4);//添加回文数
				}
			}
		}
	}sort(v.begin(), v.end());//排序
} 
bool check(int n){//判断
	if(n == 2) return 1;
	if(n < 2 || n % 2 == 0) return 0;
	for(int i = 3; i * i <= n; i += 2){
		if(n % i == 0) return 0;
	}return 1;
}
int main(){
	_init();
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < v.size() && v[i] <= m; i++){
		if(v[i] < n) continue;
		if(check(v[i])) cout << v[i] << endl;//如果是质数就输出
	}

	return 0;
}

时间复杂度： $O(n\sqrt n)$

有帮助，赞一个

去预览

0/2000

全部评论 1

复仇者_必胜啊（不加团队

help qaq

1周前来自广东

复仇者_必胜啊（不加团队

回复复仇者_必胜啊（不加团队

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define ll int
ll qmod(ll x,ll y,int m){
    ll res=1;
    x%=m;
    while(y){
        if(y&1) res=(res*x)%m;
        x=(x*x)%m;
        y>>=1;
    }
    return res;
}
bool witness(ll a,ll n){
    ll u=n-1;
    int t=0;
    while((u&1)==0) u>>=1,++t;
    ll x1,x2;
    x1=qmod(a,u,n);
    for(int i=1;i<=t;++i){
        x2=qmod(x1,2,n);
        if(x2==1 and x1!=1 and x1!=n-1) return true;
        x1=x2;
    }
    if(x1!=1) return true;
    return false;
}
bool miller_rabin(ll n,int s){
    if(n<2) return false;
    if(n==2) return true;
    if(!(n&1)) return false;
    for(int i=0;i<s and i<n;++i){
        ll a=rand()%(n-1)+1;
        if(witness(a,n)) return false;
    }
    return true;
}
vector<int>v;
void init(){
    v.push_back(11);
    for(int i=1;i<=9;i+=2){
        v.push_back(i);
        for(int j=0;j<=9;++j){
            v.push_back(i*100+j*10+i);
            for(int k=0;k<=9;++k){
                v.push_back(i*10000+j*100+k*100+j*10+i);
                for(int o=0;o<=9;++o){
                    v.push_back(i*1000000+j*100000+k*10000+o*1000+k*100+j*10+i);
                }
            }
        }
    }
    sort(v.begin(),v.end());
}
inline int read(){
    int sum=0,f=1;
    char ch=getchar();
    while(ch<'0' or ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' and ch<='9'){
        sum=(sum<<1)+(sum<<3)+(ch^48);
        ch=getchar();
    }
    return sum*f;
}
void write(int x){
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int main(void){
    init();
    srand(time(NULL));
    int a,b;
    a=read();
    b=read();
    for(int i=0;i<v.size() and v[i]<=b;++i){
        if(v[i]<a) continue; 
        int s=50;
        if(!miller_rabin(v[i],s)) continue;
        write(v[i]);
        puts("");
    }
}

1周前来自广东

‮队团加不）ด้้童帅_者仇复
回复复仇者_必胜啊（不加团队
不是……哥们……

1周前来自广东
0
‮队团加不）ด้้童帅_者仇复
回复复仇者_必胜啊（不加团队
不至于吧

1周前来自广东
0