题解

190 条题解

  • 1
    @ 2019-08-01 09:17:33

    打表
    时间快到飞起(最慢13ms)
    #include <bits/stdc++.h>
    using namespace std;
    int a[]={0,5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,98689,1003001,1008001,1022201,1028201,1035301,1043401,1055501,1062601,1065601,1074701,1082801,1085801,1092901,1093901,1114111,1117111,1120211,1123211,1126211,1129211,1134311,1145411,1150511,1153511,1160611,1163611,1175711,1177711,1178711,1180811,1183811,1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,1218121,1221221,1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,1268621,1273721,1276721,1278721,1280821,1281821,1286821,1287821,1300031,1303031,1311131,1317131,1327231,1328231,1333331,1335331,1338331,1343431,1360631,1362631,1363631,1371731,1374731,1390931,1407041,1409041,1411141,1412141,1422241,1437341,1444441,1447441,1452541,1456541,1461641,1463641,1464641,1469641,1486841,1489841,1490941,1496941,1508051,1513151,1520251,1532351,1535351,1542451,1548451,1550551,1551551,1556551,1557551,1565651,1572751,1579751,1580851,1583851,1589851,1594951,1597951,1598951,1600061,1609061,1611161,1616161,1628261,1630361,1633361,1640461,1643461,1646461,1654561,1657561,1658561,1660661,1670761,1684861,1685861,1688861,1695961,1703071,1707071,1712171,1714171,1730371,1734371,1737371,1748471,1755571,1761671,1764671,1777771,1793971,1802081,1805081,1820281,1823281,1824281,1826281,1829281,1831381,1832381,1842481,1851581,1853581,1856581,1865681,1876781,1878781,1879781,1880881,1881881,1883881,1884881,1895981,1903091,1908091,1909091,1917191,1924291,1930391,1936391,1941491,1951591,1952591,1957591,1958591,1963691,1968691,1969691,1970791,1976791,1981891,1982891,1984891,1987891,1988891,1993991,1995991,1998991,3001003,3002003,3007003,3016103,3026203,3064603,3065603,3072703,3073703,3075703,3083803,3089803,3091903,3095903,3103013,3106013,3127213,3135313,3140413,3155513,3158513,3160613,3166613,3181813,3187813,3193913,3196913,3198913,3211123,3212123,3218123,3222223,3223223,3228223,3233323,3236323,3241423,3245423,3252523,3256523,3258523,3260623,3267623,3272723,3283823,3285823,3286823,3288823,3291923,3293923,3304033,3305033,3307033,3310133,3315133,3319133,3321233,3329233,3331333,3337333,3343433,3353533,3362633,3364633,3365633,3368633,3380833,3391933,3392933,3400043,3411143,3417143,3424243,3425243,3427243,3439343,3441443,3443443,3444443,3447443,3449443,3452543,3460643,3466643,3470743,3479743,3485843,3487843,3503053,3515153,3517153,3528253,3541453,3553553,3558553,3563653,3569653,3586853,3589853,3590953,3591953,3594953,3601063,3607063,3618163,3621263,3627263,3635363,3643463,3646463,3670763,3673763,3680863,3689863,3698963,3708073,3709073,3716173,3717173,3721273,3722273,3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,3769673,3773773,3774773,3781873,3784873,3792973,3793973,3799973,3804083,3806083,3812183,3814183,3826283,3829283,3836383,3842483,3853583,3858583,3863683,3864683,3867683,3869683,3871783,3878783,3893983,3899983,3913193,3916193,3918193,3924293,3927293,3931393,3938393,3942493,3946493,3948493,3964693,3970793,3983893,3991993,3994993,3997993,3998993,7014107,7035307,7036307,7041407,7046407,7057507,7065607,7069607,7073707,7079707,7082807,7084807,7087807,7093907,7096907,7100017,7114117,7115117,7118117,7129217,7134317,7136317,7141417,7145417,7155517,7156517,7158517,7159517,7177717,7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,7257527,7261627,7267627,7276727,7278727,7291927,7300037,7302037,7310137,7314137,7324237,7327237,7347437,7352537,7354537,7362637,7365637,7381837,7388837,7392937,7401047,7403047,7409047,7415147,7434347,7436347,7439347,7452547,7461647,7466647,7472747,7475747,7485847,7486847,7489847,7493947,7507057,7508057,7518157,7519157,7521257,7527257,7540457,7562657,7564657,7576757,7586857,7592957,7594957,7600067,7611167,7619167,7622267,7630367,7632367,7644467,7654567,7662667,7665667,7666667,7668667,7669667,7674767,7681867,7690967,7693967,7696967,7715177,7718177,7722277,7729277,7733377,7742477,7747477,7750577,7758577,7764677,7772777,7774777,7778777,7782877,7783877,7791977,7794977,7807087,7819187,7820287,7821287,7831387,7832387,7838387,7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,7897987,7913197,7916197,7930397,7933397,7935397,7938397,7941497,7943497,7949497,7957597,7958597,7960697,7977797,7984897,7985897,7987897,7996997,9002009,9015109,9024209,9037309,9042409,9043409,9045409,9046409,9049409,9067609,9073709,9076709,9078709,9091909,9095909,9103019,9109019,9110119,9127219,9128219,9136319,9149419,9169619,9173719,9174719,9179719,9185819,9196919,9199919,9200029,9209029,9212129,9217129,9222229,9223229,9230329,9231329,9255529,9269629,9271729,9277729,9280829,9286829,9289829,9318139,9320239,9324239,9329239,9332339,9338339,9351539,9357539,9375739,9384839,9397939,9400049,9414149,9419149,9433349,9439349,9440449,9446449,9451549,9470749,9477749,9492949,9493949,9495949,9504059,9514159,9526259,9529259,9547459,9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,9602069,9604069,9610169,9620269,9624269,9626269,9632369,9634369,9645469,9650569,9657569,9670769,9686869,9700079,9709079,9711179,9714179,9724279,9727279,9732379,9733379,9743479,9749479,9752579,9754579,9758579,9762679,9770779,9776779,9779779,9781879,9782879,9787879,9788879,9795979,9801089,9807089,9809089,9817189,9818189,9820289,9822289,9836389,9837389,9845489,9852589,9871789,9888889,9889889,9896989,9902099,9907099,9908099,9916199,9918199,9919199,9921299,9923299,9926299,9927299,9931399,9932399,9935399,9938399,9957599,9965699,9978799,9980899,9981899,9989899};
    bool b[10000000];
    int main()
    {
    int m,n;
    cin>>m>>n;
    memset(b,false,sizeof(b));
    for(int i=1;i<=10000000;i++)
    {
    b[a[i]]=true;
    if(a[i]==0)
    {
    break;
    }
    }
    for(int i=m;i<=n;i++)
    {
    if(b[i]==true)
    {
    printf("%d\n",i);
    }
    if(i>9989899)
    {
    break;
    }
    }
    }

  • 1
    @ 2019-07-25 15:52:43

    1、求回文数:首先判断数字i有多少位(a),然后比较最高位(i/10^a)和最低位(i%10)是否相等,相等的话就把最高位和最低位去掉
    2、因为m最小为5,所以大可不必去搜索偶数,也就是说for(i=m;i<n;i+=2)就可以缩小一半范围!(但是你要先判断m是不是偶数,是的话就先+1)
    #include <iostream>
    #include <string>
    #include <cmath>
    using namespace std;
    bool sushu(int i)
    {
    int j;bool s=true;
    if(i%2==0) s=false;
    for(j=3;j<=sqrt(i);j+=2) if(i%j==0) {s=false;break;}
    return s;
    }
    bool huiwen(int i)
    {
    bool hw=true;int j,k=1,l,a,x=i,y;
    while(x/10!=0) {x=x/10;k++;}
    y=k;
    x=i;
    for(j=1;j<=k/2;j++)
    {
    a=1;
    for(l=1;l<y;l++) a=a*10;
    if(x%10==x/a) {x-=x/a*a;x=x/10;y-=2;} else {hw=false;break;}
    }
    return hw;
    }
    int main()
    {
    int m,n,i=0;
    cin>>m>>n;
    if(m%2==0) m++;
    for(i=m;i<=n;i+=2) if(huiwen(i)) if(sushu(i)) cout<<i<<endl;
    return 0;
    }

  • 1
    @ 2017-09-22 17:19:00

    虽然代码写得很丑( • ̀ω•́ )✧ 但在输出时略加操作居然过了ヾ(o・ω・)ノ 真是道难题呢!

    (:з」∠)

    算法:

    枚举生成数每一位(数组存)的**DFS**,加上**剪枝**。

    重点:

    1.既然我们所求的是回文数,那我们为什么直接求它的一半呢?
    (规避了回文数判断的问题,大力缩小搜索范围。)
    当我们想要得到我们的回文数字时,只需要按 "复制这一半" 和 "复制一半并中间数字重叠" 两种方式即可去判断素数了。

    2.不存在 "2....2" "4....4” "4....4" "5....5" "6....6" "8....8" 这一类的数字。
    (因此我们可以在搜索的最初展开时减掉大量不必的情况。)
    因为那上面形式的数很明显不是素数啦。

    3.一定要当数字的长度在N与M之间时再判断是否合法。
    (因为合成数字的操作很费时间!)
    ( 。ω。) 其实是程序写的辣鸡啦。

    可优化之处:

    1. 比如判素数来个miller-rabin。
    2. DFS写得机灵点。
    3. 不如直接打个表吧。(素数表,答案表...)

    最后劝一句,请各位不要忽视搜索的技巧。

    #include <map>
    #include <cmath>
    #include <ctime>
    #include <queue>
    #include <stack>
    #include <cstdio>
    #include <vector>
    #include <bitset>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #define LL long long
    #define INF (0x3f3f3f3f)
    #define LINF (0x3f3f3f3f3f3f3f3fLL)
    using namespace std;
    int L,R;
    vector<int> Num,Ans;
    bool CHECK1 (int num) 
    {
        vector<int> numb;
        while(num>0) {
            numb.push_back(num%10); 
            num/=10;
        }
        int len=numb.size();
        if (len%2) 
        {
            for(int i=0;i<len/2;i++)    
                if(numb[i]!=numb[len-i-1]) return 0;
        }
        else 
        {
            for(int i=0;i<len/2;i++)    
                if(numb[i]!=numb[len-i-1]) return 0;    
        }
        return 1;
    }
    bool CHECK2 (int num) 
    {
        int sqr=sqrt(num);
        for(int i=2;i<=sqr;i++) 
            if(num%i==0) return 0;
        return 1;    
    }
    int COUNT1 () 
    {
        int num=0,len=Num.size();
        while(len>0) 
        {
            num=num*10+Num[Num.size()-len];
            len--;
        }
        len=Num.size()-1;
        while(len>=0) 
        {
            num=num*10+Num[len];
            len--;
        }
        return num;
    }
    int COUNT2 () 
    {
        int num=0,len=Num.size();
        while(len>0) 
        {
            num=num*10+Num[Num.size()-len];
            len--;
        }
        len=Num.size()-2;
        while(len>=0) 
        {
            num=num*10+Num[len];
            len--;
        }
        return num;
    }
    void DFS(int len,int lenl,int lenr) 
    {   
        if(len*2>=lenl&&len*2-1<=lenr) {
            int num1=COUNT1(),num2=COUNT2();
            if(num1<=R&&num1>=L) 
                if(CHECK1(num1)) 
                    if(CHECK2(num1)) Ans.push_back(num1);
            if(num2<=R&&num2>=L) 
                if(CHECK1(num2)) 
                    if(CHECK2(num2)) Ans.push_back(num2);
            if(num1>R&&num2>R) return;
        }
        if (len*2-1>lenr) return;
        for(int i=0;i<=9;i++) {
            if(len==0) 
                if (i==0||i==2||i==4||i==6||i==8||i==5) continue;
            Num.push_back(i);
            DFS(len+1,lenl,lenr);
            Num.pop_back(); 
        }
    } 
    int main ()
    {
        cin>>L>>R;
        DFS(0,(int)(log(L)/log(10))+1,(int)(log(R)/log(10))+1);
        if(L<=5) Ans.push_back(5);
        sort(Ans.begin(),Ans.end());
        for(int i=0;i<Ans.size();i++) 
            if (Ans[i]>=5) cout<<Ans[i]<<endl; 
        return 0;
    }
    
  • 0
    @ 2018-04-11 19:33:52

    没什么需要特别注意的,直接dfs就可以,感觉此题是素数肋骨的加强版
    5和7输不出来需要特判一下
    但是下面给的代码会MLE最后一个点,因为我用的是欧拉筛判素,然后就被完美的卡掉了,改成朴素的根号n判素就可过(但是我懒)

    #include<iostream>
    #include<algorithm>
    using namespace std;
    int c[6],ans[20010],s[100000010];
    int n,m,now,len;
    void dfs(int w)
    {
        if(2*w>=len)
         return ;
        int i,sum1=0,sum2=0,lin=1,lin1,j,sum;
        if(c[w]&1)
        {
        for(i=w;i>=1;i--)
         {
            sum1+=lin*c[i];
            lin*=10;
         }
         lin1=lin;
        for(i=1;i<=w;i++)
         {
            sum2+=lin*c[i];
            lin*=10;
         }
        if(sum1+sum2>=n&&sum1+sum2<=m) 
         if(!s[sum1+sum2])
         { 
            now++;
            ans[now]=sum1+sum2;
         }
    
         for(i=0;i<=9;i++)
          {
            sum=0;
            sum=sum1+lin1*i+sum2*10;
            if(sum>=n&&sum<=m)
             if(!s[sum])
              {
                now++;
                ans[now]=sum;
              }
          }
         
        }
        for(i=0;i<=9;i++)
        {
            c[w+1]=i;
            dfs(w+1);
            c[w+1]=0;
        }
    }
    int main()
    {
        int i,j,ha=1;
        cin>>n>>m;
        for(i=1;;i++)
        {
            ha*=10;
            if(ha>=m)
             break;
        }
        len=i;
        s[1]=1;
        for(i=2;i<=m;i++)
         {
          if(!s[i])
           for(j=2;j*i<=m;j++)
            s[i*j]=1;
         }
         if(5>=n&&5<=m)
         cout<<5<<endl;
        if(7>=n&&7<=m)
         cout<<7<<endl;
        dfs(0);
        sort(ans+1,ans+now+1);
        for(i=1;i<=now;i++)
         cout<<ans[i]<<endl;
        return 0;
    }
    
  • 0
    @ 2017-07-03 18:55:35

    真几把骚,楼下的m=min(m,10000000)厉害了
    直接上素数筛

    #include<stdio.h>
    #include<algorithm>
    using namespace std;
    int n,m,w[20000000],t;
    bool vis[100000010]={0};
    void prime(){
        for(int i=2;i<=m;++i){
            if(!vis[i]) w[t++]=i;
            for(int j=0;j<t&&i*w[j]<=m;++j){
                vis[i*w[j]]=1;
                if(i%w[j]==0) break;
            }
        }
    }
    inline bool ok(int x){
        int s[10],l=0;
        for(;x;x/=10) s[l++]=x%10;
        for(int i=0;i<(l>>1);++i) if(s[i]!=s[l-i-1]) return 0;
        return 1;
    }
    int main(){
        scanf("%d%d",&n,&m); prime();
        int i=lower_bound(w,w+t,n)-w;
        while(w[i]<n) i++;
        for(;i<t;++i) if(ok(w[i])) printf("%d\n",w[i]);
    }
    
    • @ 2017-11-21 16:54:20

      ###卧槽,你这数组能tm开下?

  • 0
    @ 2017-06-13 19:47:08

    import java.util.Scanner;

    public class Test {
    public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    String in = input.nextLine();
    String[] nums = in.split(" ");
    int M = Integer.parseInt(nums[0]);
    int N = Integer.parseInt(nums[1]);
    for(int i = M;i <= N;i++){
    if(isPrime(i) && isAntitone(i)){
    System.out.println(i);
    }
    }
    }

    private static boolean isAntitone(int i) {
    boolean flag = true;
    String temp = i+"";
    char[] cs = temp.toCharArray();
    int length = cs.length;
    for(int j = 0;j < length/2;j++){
    if(cs[j] != cs[length-1-j]){
    flag = false;
    break;
    }
    }
    return flag;
    }

    private static boolean isPrime(int i) {
    boolean flag = true;
    for (int j = 2; j < i; j++) {
    if (0 == i % j) {
    flag = false;
    break;
    }
    }
    return flag;
    }
    }

  • 0
    @ 2016-11-28 15:07:11

    #include<stdio.h>

    #include<string.h>

    int prime[4000];

    int psize;

    int from, to;

    void getPrime(){

    memset(prime, 0, sizeof(prime));

    psize = 0;

    int i,j;

    bool a[10000];

    memset(a, -1, sizeof(a));

    for (i = 2; i < 10000; i++){

    if (!a[i])continue;

    prime[psize++] = i;

    for (j = i + i; j < 10000; j+=i)a[j] = false;

    }

    }

    bool isPrime(int n){

    int i;

    for (i = 0;prime[i]*prime[i]<=n; i++)if (n%prime[i] == 0)return false;

    return true;

    }

    void one(){

    if (from>7)return;

    if (from == 5)printf("5\n");

    printf("7\n");

    }

    void three(){

    if (from > 999)return;

    int i, j,k;

    int a[4] = { 1, 3, 7, 9 };

    for (i = 0; i < 4;i++)

    for (j = 0; j < 10; j++){

    k = a[i] * 100 + j * 10 + a[i];

    if ( k< from)continue;

    if (k>to)return;

    if (isPrime(k))printf("%d%d%d\n", a[i], j,a[ i]);

    }

    }

    void five(){

    if (from>99999)return;

    int a[4] = { 1, 3, 7, 9 };

    int i, j, k, l;

    for (i = 0; i < 4;i++)

    for (j = 0; j < 10;j++)

    for (k = 0; k < 10; k++){

    l = a[i] * 10000 + j * 1000 + k * 100 + j * 10 + a[i];

    if (l<from)continue;
    if (l>to)return;

    if (isPrime(l))printf("%d%d%d%d%d\n", a[i], j, k, j, a[i] );

    }

    }

    void seven(){

    if (from>9999999)return;

    int a[4] = { 1, 3, 7, 9 };

    int i, j, k, l,m;

    for (i = 0; i < 4; i++)

    for (j = 0; j < 10; j++)

    for (k = 0; k < 10; k++)

    for(m=0;m<10;m++){
    l = a[i] * 1000000 + j * 100000 + k * 10000 + m * 1000 +k*100+j*10+ a[i];
    if (l<from)continue;
    if (l>to)return;

    if (isPrime(l))printf("%d%d%d%d%d%d%d\n", a[i], j, k,m,k, j, a[i]);

    }

    }

    int main(){

    getPrime();

    prime[psize++]=10001;

    scanf("%d%d", &from, &to);

    one();

    if (11 >= from && 11 <= to)printf("11\n");

    three(); five(); seven();

    return 0;

    }

  • 0
    @ 2016-11-16 11:04:25
    #include<bits/stdc++.h>
    using namespace std;
    bool check(int i)
    {
        for(int j=2;j*j<=i;j++) {
            if(i%j==0) return 0;
        }
        return 1;
    }
    bool huiwen(int i)
    {
        int k=i,l=0;
        int a[11];
        for(int j=0;k>0;k/=10,j++) l++,a[j]=k%10;
        for(int j=0,k=l-1;j<(l+1)/2;j++,k--) {
            if(a[j]!=a[k]) return 0;
        }
        return 1;
    }
    int main()
    {
        int i,j,k,l,n,m;
        cin>>n>>m;
        m = min(m,10000000);
        for(i=n;i<=m;i++) {
            if(i>3&&i%10!=2){
                if(huiwen(i)) {
                    if(check(i)) cout<<i<<endl;
                }
            }
            
        }
        return 0;
    }
    
    
    • @ 2019-01-30 13:57:35

      m = min(m,10000000);太强了!

  • 0
    @ 2016-11-04 09:25:52

    真的是醉了。。。

    #include<bits/stdc++.h>
    #define pi acos(-1.0)
    #define ll long long
    #define N 11
    #define INF 0x7fffffff
    using namespace std;
    int a[N];

    bool check(int x)
    {
    int len=0,b=x,c=x;
    while(b)
    {
    b/=10;
    len++;
    }
    if(!len%2)
    return false;
    if(!x%2)
    return false;
    memset(a,0,sizeof(a));
    for(int i=1;i<=len;i++)
    {
    a[i]=x%10;
    x/=10;
    }
    for(int i=1;i<=(len+1)/2;i++)
    {
    if(a[i]!=a[len+1-i])
    return false;
    }
    for(int i=2;i<=sqrt(c);i++)
    if(c%i==0)
    return false;
    return true;
    }
    int main()
    {
    int L,R;
    scanf("%d%d",&L,&R);
    R=min(R,10000000);
    for(int i=L;i<=R;i++)
    {
    if(check(i))
    printf("%d\n",i);

    }
    return 0;
    }

  • 0
    @ 2016-08-20 22:35:37

    #include <cstdio>

    int A[]={1,2,3,5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,98689,1003001,1008001,1022201,1028201,1035301,1043401,1055501,1062601,1065601,1074701,1082801,1085801,1092901,1093901,1114111,1117111,1120211,1123211,1126211,1129211,1134311,1145411,1150511,1153511,1160611,1163611,1175711,1177711,1178711,1180811,1183811,1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,1218121,1221221,1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,1268621,1273721,1276721,1278721,1280821,1281821,1286821,1287821,1300031,1303031,1311131,1317131,1327231,1328231,1333331,1335331,1338331,1343431,1360631,1362631,1363631,1371731,1374731,1390931,1407041,1409041,1411141,1412141,1422241,1437341,1444441,1447441,1452541,1456541,1461641,1463641,1464641,1469641,1486841,1489841,1490941,1496941,1508051,1513151,1520251,1532351,1535351,1542451,1548451,1550551,1551551,1556551,1557551,1565651,1572751,1579751,1580851,1583851,1589851,1594951,1597951,1598951,1600061,1609061,1611161,1616161,1628261,1630361,1633361,1640461,1643461,1646461,1654561,1657561,1658561,1660661,1670761,1684861,1685861,1688861,1695961,1703071,1707071,1712171,1714171,1730371,1734371,1737371,1748471,1755571,1761671,1764671,1777771,1793971,1802081,1805081,1820281,1823281,1824281,1826281,1829281,1831381,1832381,1842481,1851581,1853581,1856581,1865681,1876781,1878781,1879781,1880881,1881881,1883881,1884881,1895981,1903091,1908091,1909091,1917191,1924291,1930391,1936391,1941491,1951591,1952591,1957591,1958591,1963691,1968691,1969691,1970791,1976791,1981891,1982891,1984891,1987891,1988891,1993991,1995991,1998991,3001003,3002003,3007003,3016103,3026203,3064603,3065603,3072703,3073703,3075703,3083803,3089803,3091903,3095903,3103013,3106013,3127213,3135313,3140413,3155513,3158513,3160613,3166613,3181813,3187813,3193913,3196913,3198913,3211123,3212123,3218123,3222223,3223223,3228223,3233323,3236323,3241423,3245423,3252523,3256523,3258523,3260623,3267623,3272723,3283823,3285823,3286823,3288823,3291923,3293923,3304033,3305033,3307033,3310133,3315133,3319133,3321233,3329233,3331333,3337333,3343433,3353533,3362633,3364633,3365633,3368633,3380833,3391933,3392933,3400043,3411143,3417143,3424243,3425243,3427243,3439343,3441443,3443443,3444443,3447443,3449443,3452543,3460643,3466643,3470743,3479743,3485843,3487843,3503053,3515153,3517153,3528253,3541453,3553553,3558553,3563653,3569653,3586853,3589853,3590953,3591953,3594953,3601063,3607063,3618163,3621263,3627263,3635363,3643463,3646463,3670763,3673763,3680863,3689863,3698963,3708073,3709073,3716173,3717173,3721273,3722273,3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,3769673,3773773,3774773,3781873,3784873,3792973,3793973,3799973,3804083,3806083,3812183,3814183,3826283,3829283,3836383,3842483,3853583,3858583,3863683,3864683,3867683,3869683,3871783,3878783,3893983,3899983,3913193,3916193,3918193,3924293,3927293,3931393,3938393,3942493,3946493,3948493,3964693,3970793,3983893,3991993,3994993,3997993,3998993,7014107,7035307,7036307,7041407,7046407,7057507,7065607,7069607,7073707,7079707,7082807,7084807,7087807,7093907,7096907,7100017,7114117,7115117,7118117,7129217,7134317,7136317,7141417,7145417,7155517,7156517,7158517,7159517,7177717,7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,7257527,7261627,7267627,7276727,7278727,7291927,7300037,7302037,7310137,7314137,7324237,7327237,7347437,7352537,7354537,7362637,7365637,7381837,7388837,7392937,7401047,7403047,7409047,7415147,7434347,7436347,7439347,7452547,7461647,7466647,7472747,7475747,7485847,7486847,7489847,7493947,7507057,7508057,7518157,7519157,7521257,7527257,7540457,7562657,7564657,7576757,7586857,7592957,7594957,7600067,7611167,7619167,7622267,7630367,7632367,7644467,7654567,7662667,7665667,7666667,7668667,7669667,7674767,7681867,7690967,7693967,7696967,7715177,7718177,7722277,7729277,7733377,7742477,7747477,7750577,7758577,7764677,7772777,7774777,7778777,7782877,7783877,7791977,7794977,7807087,7819187,7820287,7821287,7831387,7832387,7838387,7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,7897987,7913197,7916197,7930397,7933397,7935397,7938397,7941497,7943497,7949497,7957597,7958597,7960697,7977797,7984897,7985897,7987897,7996997,9002009,9015109,9024209,9037309,9042409,9043409,9045409,9046409,9049409,9067609,9073709,9076709,9078709,9091909,9095909,9103019,9109019,9110119,9127219,9128219,9136319,9149419,9169619,9173719,9174719,9179719,9185819,9196919,9199919,9200029,9209029,9212129,9217129,9222229,9223229,9230329,9231329,9255529,9269629,9271729,9277729,9280829,9286829,9289829,9318139,9320239,9324239,9329239,9332339,9338339,9351539,9357539,9375739,9384839,9397939,9400049,9414149,9419149,9433349,9439349,9440449,9446449,9451549,9470749,9477749,9492949,9493949,9495949,9504059,9514159,9526259,9529259,9547459,9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,9602069,9604069,9610169,9620269,9624269,9626269,9632369,9634369,9645469,9650569,9657569,9670769,9686869,9700079,9709079,9711179,9714179,9724279,9727279,9732379,9733379,9743479,9749479,9752579,9754579,9758579,9762679,9770779,9776779,9779779,9781879,9782879,9787879,9788879,9795979,9801089,9807089,9809089,9817189,9818189,9820289,9822289,9836389,9837389,9845489,9852589,9871789,9888889,9889889,9896989,9902099,9907099,9908099,9916199,9918199,9919199,9921299,9923299,9926299,9927299,9931399,9932399,9935399,9938399,9957599,9965699,9978799,9980899,9981899,9989899};

    int main(){
    int l,r,flag=0;
    scanf("%d%d",&l,&r);
    for(int i=0;i<782;i++){
    int t=A[i];
    if(A[i]>=l&&A[i]<=r)

    flag=1;
    if(A[i]>r)
    break;
    if(flag==1)
    printf("%d\n",A[i]);
    }
    return 0;
    }

  • 0
    @ 2016-08-19 20:45:52

    #include <iostream>
    #include <cstdio>
    #include <math.h>
    #include <stdlib.h>
    #include <algorithm>
    #define ll long long
    using namespace std;
    const int S=50;//随机算法判定次数,S越大,判错概率越小

    //计算 (a*b)%c. a,b都是long long的数,直接相乘可能溢出的
    // a,b,c <2^63
    long long mult_mod(long long a,long long b,long long c)
    {
    a%=c;
    b%=c;
    long long ret=0;
    while(b)
    {
    if(b&1){ret+=a;ret%=c;}
    a<<=1;
    if(a>=c)a%=c;
    b>>=1;
    }
    return ret;
    }

    //计算 x^n %c
    long long pow_mod(long long x,long long n,long long mod)//x^n%c
    {
    if(n==1)return x%mod;
    x%=mod;
    long long tmp=x;
    long long ret=1;
    while(n)
    {
    if(n&1) ret=mult_mod(ret,tmp,mod);
    tmp=mult_mod(tmp,tmp,mod);
    n>>=1;
    }
    return ret;
    }

    //以a为基,n-1=x*2^t a^(n-1)=1(mod n) 验证n是不是合数
    //一定是合数返回true,不一定返回false
    bool check(long long a,long long n,long long x,long long t)
    {
    long long ret=pow_mod(a,x,n);
    long long last=ret;
    for(int i=1;i<=t;i++)
    {
    ret=mult_mod(ret,ret,n);
    if(ret==1&&last!=1&&last!=n-1) return true;//合数
    last=ret;
    }
    if(ret!=1) return true;
    return false;
    }

    // Miller_Rabin()算法素数判定
    //是素数返回true.(可能是伪素数,但概率极小)
    //合数返回false;

    bool Miller_Rabin(long long n)
    {
    if(n<2)return false;
    if(n==2)return true;
    if((n&1)==0) return false;//偶数
    long long x=n-1;
    long long t=0;
    while((x&1)==0){x>>=1;t++;}
    for(int i=0;i<S;i++)
    {
    long long a=rand()%(n-1)+1;//rand()需要stdlib.h头文件
    if(check(a,n,x,t))
    return false;//合数
    }
    return true;
    }

    ll pw10[10];
    int ans[100000];
    int main()
    {
    int n,m;
    int cnt=0;
    pw10[0]=1;
    for (int i=1;i<=10;i++)
    pw10[i]=pw10[i-1]*10;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=10000;i++)
    {
    ll temp=i;
    ll sum=0;
    int level=0;
    while (temp>0)
    {
    sum=sum*10+ temp % 10;
    temp/=10;
    level++;
    }
    temp=i*pw10[level]+sum;
    if (temp>=n && temp<=m && Miller_Rabin(temp))
    ans[cnt++]=temp;

    for (int k=0;k<=9;k++)
    {
    temp=i*pw10[level+1]+k*pw10[level]+sum;
    if (temp>=n && temp<=m && Miller_Rabin(temp))
    ans[cnt++]=temp;
    }
    }

    if ( 5>=n && 5<=m) ans[cnt++]=5;
    if ( 7>=n && 7<=m) ans[cnt++]=7;
    sort(ans,ans+cnt);
    for (int i=0;i<cnt;i++)
    printf("%d\n",ans[i]);
    return 0;
    }

  • 0
    @ 2016-07-21 22:17:30

    打什么表啊?

    记录信息
    评测状态    Accepted
    题目  P1042 捕风捉影
    递交时间    2016-07-21 22:14:19
    代码语言    C++
    评测机 ShadowShore
    消耗时间    1888 ms
    消耗内存    556 KiB
    评测时间    2016-07-21 22:14:22
    评测结果
    编译成功
    
    测试数据 #0: Accepted, time = 0 ms, mem = 548 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 552 KiB, score = 10
    测试数据 #2: Accepted, time = 62 ms, mem = 552 KiB, score = 10
    测试数据 #3: Accepted, time = 62 ms, mem = 556 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 552 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 548 KiB, score = 10
    测试数据 #6: Accepted, time = 625 ms, mem = 552 KiB, score = 10
    测试数据 #7: Accepted, time = 546 ms, mem = 552 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 552 KiB, score = 10
    测试数据 #9: Accepted, time = 593 ms, mem = 552 KiB, score = 10
    Accepted, time = 1888 ms, mem = 556 KiB, score = 100
    代码
    #include <bits/stdc++.h>
    bool check(int x) {
      int len = 0,b = x,c = x;
      for (;b;len++) b /= 10;
      if(!len%2) return false;
      int a[101];
      if (!x%2) return false;
      memset(a,0,sizeof(a));
      for(int i = 1;i <= len;i++) {
        a[i] = x%10;
        x /= 10;
      }
      for (int i = 1;i <= (len+1)/2;i++)
        if (a[i] != a[len+1-i]) return false;
      for (int i = 2;i <= sqrt(c);i++)
        if(c%i==0) return false;
      return true;
    }
    int main() {
      int L,R;
      scanf("%d%d",&L,&R);
      R = std :: min(R,10000000);
      for (int i = L;i <= R;i++)
        if (check(i)) printf("%d\n",i);
      return 0;
    }
    
  • 0
    @ 2016-07-21 16:27:22

    不明白为什么这种题会有人要打表... 还有拜托打表的人也得把表弄对,居然把 0 和 1 当素数、2 当合数,实在无语。
    随便写个DFS 10^10内秒杀无压力

    #include <stdio.h>
    #include <math.h>

    int num[15]; //DFS时记录回文数数码
    int a, b; //题中所给区间端点

    int isPrime(int x){
    int i, bound = ceil(sqrt(x));
    if(x == 2)
    return 1;
    if(x <= 1)
    return 0;
    for(i=2; i<=bound; i++){
    if(x%i == 0)
    return 0;
    }
    return 1;
    }
    void print(const int length){
    //将 num 数组还原成数,然后验证合法性
    int n, i;
    for(n=0, i=0; i<=(length-1)/2; i++)
    n = n*10 + num[i];
    for(; i<length; i++)
    n = n*10 + num[length-i-1]; //补全剩下一半
    if(n>=a && n<=b && isPrime(n))
    printf("%d\n", n);
    }
    void search(const int length, int index){
    //生成长度为length的回文数的前半部分,将每一位都记录到num数组。index代表枚举到第几位。
    //注意枚举到长度的一半即可,剩下一半与前面一半对称
    int i;
    if(length <= index*2){
    print(length);
    return;
    }
    for(i=0; i<10; i++){
    if(i%2==0 && index==0 && length>1)
    continue;
    num[index] = i;
    search(length, index+1);
    }
    }
    int main(){
    int c, d; //分别代表 a 和 b 的位数
    scanf("%d %d", &a, &b);
    c = (int)(log(a)/log(10))+1;
    d = (int)(log(b)/log(10))+1;
    for(; c<=d; c++)
    search(c, 0);
    return 0;
    }

    • @ 2017-09-22 15:57:42

      枚举一半的想法很厉害。

  • 0
    @ 2016-05-05 20:50:19

    var
    a:array [1..780] of longint=(0,5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,98689,1003001,1008001,1022201,1028201,1035301,1043401,1055501,1062601,1065601,1074701,1082801,1085801,1092901,1093901,1114111,1117111,1120211,1123211,1126211,1129211,1134311,1145411,1150511,1153511,1160611,1163611,1175711,1177711,1178711,1180811,1183811,1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,1218121,1221221,1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,1268621,1273721,1276721,1278721,1280821,1281821,1286821,1287821,1300031,1303031,1311131,1317131,1327231,1328231,1333331,1335331,1338331,1343431,1360631,1362631,1363631,1371731,1374731,1390931,1407041,1409041,1411141,1412141,1422241,1437341,1444441,1447441,1452541,1456541,1461641,1463641,1464641,1469641,1486841,1489841,1490941,1496941,1508051,1513151,1520251,1532351,1535351,1542451,1548451,1550551,1551551,1556551,1557551,1565651,1572751,1579751,1580851,1583851,1589851,1594951,1597951,1598951,1600061,1609061,1611161,1616161,1628261,1630361,1633361,1640461,1643461,1646461,1654561,1657561,1658561,1660661,1670761,1684861,1685861,1688861,1695961,1703071,1707071,1712171,1714171,1730371,1734371,1737371,1748471,1755571,1761671,1764671,1777771,1793971,1802081,1805081,1820281,1823281,1824281,1826281,1829281,1831381,1832381,1842481,1851581,1853581,1856581,1865681,1876781,1878781,1879781,1880881,1881881,1883881,1884881,1895981,1903091,1908091,1909091,1917191,1924291,1930391,1936391,1941491,1951591,1952591,1957591,1958591,1963691,1968691,1969691,1970791,1976791,1981891,1982891,1984891,1987891,1988891,1993991,1995991,1998991,3001003,3002003,3007003,3016103,3026203,3064603,3065603,3072703,3073703,3075703,3083803,3089803,3091903,3095903,3103013,3106013,3127213,3135313,3140413,3155513,3158513,3160613,3166613,3181813,3187813,3193913,3196913,3198913,3211123,3212123,3218123,3222223,3223223,3228223,3233323,3236323,3241423,3245423,3252523,3256523,3258523,3260623,3267623,3272723,3283823,3285823,3286823,3288823,3291923,3293923,3304033,3305033,3307033,3310133,3315133,3319133,3321233,3329233,3331333,3337333,3343433,3353533,3362633,3364633,3365633,3368633,3380833,3391933,3392933,3400043,3411143,3417143,3424243,3425243,3427243,3439343,3441443,3443443,3444443,3447443,3449443,3452543,3460643,3466643,3470743,3479743,3485843,3487843,3503053,3515153,3517153,3528253,3541453,3553553,3558553,3563653,3569653,3586853,3589853,3590953,3591953,3594953,3601063,3607063,3618163,3621263,3627263,3635363,3643463,3646463,3670763,3673763,3680863,3689863,3698963,3708073,3709073,3716173,3717173,3721273,3722273,3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,3769673,3773773,3774773,3781873,3784873,3792973,3793973,3799973,3804083,3806083,3812183,3814183,3826283,3829283,3836383,3842483,3853583,3858583,3863683,3864683,3867683,3869683,3871783,3878783,3893983,3899983,3913193,3916193,3918193,3924293,3927293,3931393,3938393,3942493,3946493,3948493,3964693,3970793,3983893,3991993,3994993,3997993,3998993,7014107,7035307,7036307,7041407,7046407,7057507,7065607,7069607,7073707,7079707,7082807,7084807,7087807,7093907,7096907,7100017,7114117,7115117,7118117,7129217,7134317,7136317,7141417,7145417,7155517,7156517,7158517,7159517,7177717,7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,7257527,7261627,7267627,7276727,7278727,7291927,7300037,7302037,7310137,7314137,7324237,7327237,7347437,7352537,7354537,7362637,7365637,7381837,7388837,7392937,7401047,7403047,7409047,7415147,7434347,7436347,7439347,7452547,7461647,7466647,7472747,7475747,7485847,7486847,7489847,7493947,7507057,7508057,7518157,7519157,7521257,7527257,7540457,7562657,7564657,7576757,7586857,7592957,7594957,7600067,7611167,7619167,7622267,7630367,7632367,7644467,7654567,7662667,7665667,7666667,7668667,7669667,7674767,7681867,7690967,7693967,7696967,7715177,7718177,7722277,7729277,7733377,7742477,7747477,7750577,7758577,7764677,7772777,7774777,7778777,7782877,7783877,7791977,7794977,7807087,7819187,7820287,7821287,7831387,7832387,7838387,7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,7897987,7913197,7916197,7930397,7933397,7935397,7938397,7941497,7943497,7949497,7957597,7958597,7960697,7977797,7984897,7985897,7987897,7996997,9002009,9015109,9024209,9037309,9042409,9043409,9045409,9046409,9049409,9067609,9073709,9076709,9078709,9091909,9095909,9103019,9109019,9110119,9127219,9128219,9136319,9149419,9169619,9173719,9174719,9179719,9185819,9196919,9199919,9200029,9209029,9212129,9217129,9222229,9223229,9230329,9231329,9255529,9269629,9271729,9277729,9280829,9286829,9289829,9318139,9320239,9324239,9329239,9332339,9338339,9351539,9357539,9375739,9384839,9397939,9400049,9414149,9419149,9433349,9439349,9440449,9446449,9451549,9470749,9477749,9492949,9493949,9495949,9504059,9514159,9526259,9529259,9547459,9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,9602069,9604069,9610169,9620269,9624269,9626269,9632369,9634369,9645469,9650569,9657569,9670769,9686869,9700079,9709079,9711179,9714179,9724279,9727279,9732379,9733379,9743479,9749479,9752579,9754579,9758579,9762679,9770779,9776779,9779779,9781879,9782879,9787879,9788879,9795979,9801089,9807089,9809089,9817189,9818189,9820289,9822289,9836389,9837389,9845489,9852589,9871789,9888889,9889889,9896989,9902099,9907099,9908099,9916199,9918199,9919199,9921299,9923299,9926299,9927299,9931399,9932399,9935399,9938399,9957599,9965699,9978799,9980899,9981899,9989899);
    c,b,i:longint;
    begin
    read(c,b);
    for i:=1 to 780 do
    if (a[i]>=c) and (a[i]<=b) then writeln(a[i]);
    end.

  • 0
    @ 2015-09-17 13:32:55

    总计15ms

    var m,n,s,b,x,c,v:longint;
    z:array[1..4]of longint=(1,3,7,9);

    function su(a:longint):boolean;
    var s,d:longint;
    begin
    for s:=1 to (trunc(sqrt(a)) div 2) do
    if a mod (s*2+1)=0 then exit(false);
    exit(true);
    end;

    procedure main;
    begin
    readln(m,n);

    if 5>=m then writeln(5);

    for x:=1 to 4 do
    if su(z[x]) then if (z[x]>=m) then
    if z[x]<=n then writeln(z[x]) else exit;

    if 11>=m then
    if 11<=n then writeln(11) else exit;

    for x:=1 to 4 do
    for c:=0 to 9 do
    begin
    s:=z[x]*101+c*10;
    if su(s) then if s>=m then
    if s<=n then writeln(s) else exit;
    end;

    for x:=1 to 4 do
    for c:=0 to 9 do
    begin
    s:=z[x]*1001+c*110;
    if su(s) then if s>= m then
    if s<=n then writeln(s) else exit;
    end;

    for x:=1 to 4 do
    for c:=0 to 9 do
    for v:=0 to 9 do
    begin
    s:=z[x]*10001+c*1010+v*100;
    if su(s) then if s>=m then
    if s<=n then writeln(s) else exit;
    end;

    for x:=1 to 4 do
    for c:=0 to 9 do
    for v:=0 to 9 do
    begin
    s:=z[x]*100001+c*10010+v*1100;
    if su(s) then if s>=m then
    if s<=n then writeln(s) else exit;
    end;

    for x:=1 to 4 do
    for c:=0 to 9 do
    for v:=0 to 9 do
    for b:=0 to 9 do
    begin
    s:=z[x]*1000001+c*100010+v*10100+b*1000;
    if su(s) then if s>=m then
    if s<=n then writeln(s) else exit;
    end;

    for x:=1 to 4 do
    for c:=0 to 9 do
    for v:=0 to 9 do
    for b:=0 to 9 do
    begin
    s:=z[x]*10000001+c*1000010+v*100100+b*11000;
    if su(s) then if s>=m then
    if s<=n then writeln(s) else exit;
    end;
    end;

    begin
    main;
    end.

  • 0
    @ 2015-08-10 14:25:43

    #include<cstdio>
    using namespace std;
    main()
    {
    int a[780]={0,5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,98689,1003001,1008001,1022201,1028201,1035301,1043401,1055501,1062601,1065601,1074701,1082801,1085801,1092901,1093901,1114111,1117111,1120211,1123211,1126211,1129211,1134311,1145411,1150511,1153511,1160611,1163611,1175711,1177711,1178711,1180811,1183811,1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,1218121,1221221,1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,1268621,1273721,1276721,1278721,1280821,1281821,1286821,1287821,1300031,1303031,1311131,1317131,1327231,1328231,1333331,1335331,1338331,1343431,1360631,1362631,1363631,1371731,1374731,1390931,1407041,1409041,1411141,1412141,1422241,1437341,1444441,1447441,1452541,1456541,1461641,1463641,1464641,1469641,1486841,1489841,1490941,1496941,1508051,1513151,1520251,1532351,1535351,1542451,1548451,1550551,1551551,1556551,1557551,1565651,1572751,1579751,1580851,1583851,1589851,1594951,1597951,1598951,1600061,1609061,1611161,1616161,1628261,1630361,1633361,1640461,1643461,1646461,1654561,1657561,1658561,1660661,1670761,1684861,1685861,1688861,1695961,1703071,1707071,1712171,1714171,1730371,1734371,1737371,1748471,1755571,1761671,1764671,1777771,1793971,1802081,1805081,1820281,1823281,1824281,1826281,1829281,1831381,1832381,1842481,1851581,1853581,1856581,1865681,1876781,1878781,1879781,1880881,1881881,1883881,1884881,1895981,1903091,1908091,1909091,1917191,1924291,1930391,1936391,1941491,1951591,1952591,1957591,1958591,1963691,1968691,1969691,1970791,1976791,1981891,1982891,1984891,1987891,1988891,1993991,1995991,1998991,3001003,3002003,3007003,3016103,3026203,3064603,3065603,3072703,3073703,3075703,3083803,3089803,3091903,3095903,3103013,3106013,3127213,3135313,3140413,3155513,3158513,3160613,3166613,3181813,3187813,3193913,3196913,3198913,3211123,3212123,3218123,3222223,3223223,3228223,3233323,3236323,3241423,3245423,3252523,3256523,3258523,3260623,3267623,3272723,3283823,3285823,3286823,3288823,3291923,3293923,3304033,3305033,3307033,3310133,3315133,3319133,3321233,3329233,3331333,3337333,3343433,3353533,3362633,3364633,3365633,3368633,3380833,3391933,3392933,3400043,3411143,3417143,3424243,3425243,3427243,3439343,3441443,3443443,3444443,3447443,3449443,3452543,3460643,3466643,3470743,3479743,3485843,3487843,3503053,3515153,3517153,3528253,3541453,3553553,3558553,3563653,3569653,3586853,3589853,3590953,3591953,3594953,3601063,3607063,3618163,3621263,3627263,3635363,3643463,3646463,3670763,3673763,3680863,3689863,3698963,3708073,3709073,3716173,3717173,3721273,3722273,3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,3769673,3773773,3774773,3781873,3784873,3792973,3793973,3799973,3804083,3806083,3812183,3814183,3826283,3829283,3836383,3842483,3853583,3858583,3863683,3864683,3867683,3869683,3871783,3878783,3893983,3899983,3913193,3916193,3918193,3924293,3927293,3931393,3938393,3942493,3946493,3948493,3964693,3970793,3983893,3991993,3994993,3997993,3998993,7014107,7035307,7036307,7041407,7046407,7057507,7065607,7069607,7073707,7079707,7082807,7084807,7087807,7093907,7096907,7100017,7114117,7115117,7118117,7129217,7134317,7136317,7141417,7145417,7155517,7156517,7158517,7159517,7177717,7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,7257527,7261627,7267627,7276727,7278727,7291927,7300037,7302037,7310137,7314137,7324237,7327237,7347437,7352537,7354537,7362637,7365637,7381837,7388837,7392937,7401047,7403047,7409047,7415147,7434347,7436347,7439347,7452547,7461647,7466647,7472747,7475747,7485847,7486847,7489847,7493947,7507057,7508057,7518157,7519157,7521257,7527257,7540457,7562657,7564657,7576757,7586857,7592957,7594957,7600067,7611167,7619167,7622267,7630367,7632367,7644467,7654567,7662667,7665667,7666667,7668667,7669667,7674767,7681867,7690967,7693967,7696967,7715177,7718177,7722277,7729277,7733377,7742477,7747477,7750577,7758577,7764677,7772777,7774777,7778777,7782877,7783877,7791977,7794977,7807087,7819187,7820287,7821287,7831387,7832387,7838387,7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,7897987,7913197,7916197,7930397,7933397,7935397,7938397,7941497,7943497,7949497,7957597,7958597,7960697,7977797,7984897,7985897,7987897,7996997,9002009,9015109,9024209,9037309,9042409,9043409,9045409,9046409,9049409,9067609,9073709,9076709,9078709,9091909,9095909,9103019,9109019,9110119,9127219,9128219,9136319,9149419,9169619,9173719,9174719,9179719,9185819,9196919,9199919,9200029,9209029,9212129,9217129,9222229,9223229,9230329,9231329,9255529,9269629,9271729,9277729,9280829,9286829,9289829,9318139,9320239,9324239,9329239,9332339,9338339,9351539,9357539,9375739,9384839,9397939,9400049,9414149,9419149,9433349,9439349,9440449,9446449,9451549,9470749,9477749,9492949,9493949,9495949,9504059,9514159,9526259,9529259,9547459,9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,9602069,9604069,9610169,9620269,9624269,9626269,9632369,9634369,9645469,9650569,9657569,9670769,9686869,9700079,9709079,9711179,9714179,9724279,9727279,9732379,9733379,9743479,9749479,9752579,9754579,9758579,9762679,9770779,9776779,9779779,9781879,9782879,9787879,9788879,9795979,9801089,9807089,9809089,9817189,9818189,9820289,9822289,9836389,9837389,9845489,9852589,9871789,9888889,9889889,9896989,9902099,9907099,9908099,9916199,9918199,9919199,9921299,9923299,9926299,9927299,9931399,9932399,9935399,9938399,9957599,9965699,9978799,9980899,9981899,9989899},m,n,i; scanf("%d%d",&m,&n); for(i=1;i<=779;i++) { if(a[i]>=m&&a[i]<=n) printf("%d\n",a[i]); if(a[i]>n) return 0; } }

  • 0
    @ 2015-08-01 10:43:44

    #include<cstdio>
    #include<iostream>
    using namespace std;
    int a[780]={0,5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,98689,1003001,1008001,1022201,1028201,1035301,1043401,1055501,1062601,1065601,1074701,1082801,1085801,1092901,1093901,1114111,1117111,1120211,1123211,1126211,1129211,1134311,1145411,1150511,1153511,1160611,1163611,1175711,1177711,1178711,1180811,1183811,1186811,1190911,1193911,1196911,1201021,1208021,1212121,1215121,1218121,1221221,1235321,1242421,1243421,1245421,1250521,1253521,1257521,1262621,1268621,1273721,1276721,1278721,1280821,1281821,1286821,1287821,1300031,1303031,1311131,1317131,1327231,1328231,1333331,1335331,1338331,1343431,1360631,1362631,1363631,1371731,1374731,1390931,1407041,1409041,1411141,1412141,1422241,1437341,1444441,1447441,1452541,1456541,1461641,1463641,1464641,1469641,1486841,1489841,1490941,1496941,1508051,1513151,1520251,1532351,1535351,1542451,1548451,1550551,1551551,1556551,1557551,1565651,1572751,1579751,1580851,1583851,1589851,1594951,1597951,1598951,1600061,1609061,1611161,1616161,1628261,1630361,1633361,1640461,1643461,1646461,1654561,1657561,1658561,1660661,1670761,1684861,1685861,1688861,1695961,1703071,1707071,1712171,1714171,1730371,1734371,1737371,1748471,1755571,1761671,1764671,1777771,1793971,1802081,1805081,1820281,1823281,1824281,1826281,1829281,1831381,1832381,1842481,1851581,1853581,1856581,1865681,1876781,1878781,1879781,1880881,1881881,1883881,1884881,1895981,1903091,1908091,1909091,1917191,1924291,1930391,1936391,1941491,1951591,1952591,1957591,1958591,1963691,1968691,1969691,1970791,1976791,1981891,1982891,1984891,1987891,1988891,1993991,1995991,1998991,3001003,3002003,3007003,3016103,3026203,3064603,3065603,3072703,3073703,3075703,3083803,3089803,3091903,3095903,3103013,3106013,3127213,3135313,3140413,3155513,3158513,3160613,3166613,3181813,3187813,3193913,3196913,3198913,3211123,3212123,3218123,3222223,3223223,3228223,3233323,3236323,3241423,3245423,3252523,3256523,3258523,3260623,3267623,3272723,3283823,3285823,3286823,3288823,3291923,3293923,3304033,3305033,3307033,3310133,3315133,3319133,3321233,3329233,3331333,3337333,3343433,3353533,3362633,3364633,3365633,3368633,3380833,3391933,3392933,3400043,3411143,3417143,3424243,3425243,3427243,3439343,3441443,3443443,3444443,3447443,3449443,3452543,3460643,3466643,3470743,3479743,3485843,3487843,3503053,3515153,3517153,3528253,3541453,3553553,3558553,3563653,3569653,3586853,3589853,3590953,3591953,3594953,3601063,3607063,3618163,3621263,3627263,3635363,3643463,3646463,3670763,3673763,3680863,3689863,3698963,3708073,3709073,3716173,3717173,3721273,3722273,3728273,3732373,3743473,3746473,3762673,3763673,3765673,3768673,3769673,3773773,3774773,3781873,3784873,3792973,3793973,3799973,3804083,3806083,3812183,3814183,3826283,3829283,3836383,3842483,3853583,3858583,3863683,3864683,3867683,3869683,3871783,3878783,3893983,3899983,3913193,3916193,3918193,3924293,3927293,3931393,3938393,3942493,3946493,3948493,3964693,3970793,3983893,3991993,3994993,3997993,3998993,7014107,7035307,7036307,7041407,7046407,7057507,7065607,7069607,7073707,7079707,7082807,7084807,7087807,7093907,7096907,7100017,7114117,7115117,7118117,7129217,7134317,7136317,7141417,7145417,7155517,7156517,7158517,7159517,7177717,7190917,7194917,7215127,7226227,7246427,7249427,7250527,7256527,7257527,7261627,7267627,7276727,7278727,7291927,7300037,7302037,7310137,7314137,7324237,7327237,7347437,7352537,7354537,7362637,7365637,7381837,7388837,7392937,7401047,7403047,7409047,7415147,7434347,7436347,7439347,7452547,7461647,7466647,7472747,7475747,7485847,7486847,7489847,7493947,7507057,7508057,7518157,7519157,7521257,7527257,7540457,7562657,7564657,7576757,7586857,7592957,7594957,7600067,7611167,7619167,7622267,7630367,7632367,7644467,7654567,7662667,7665667,7666667,7668667,7669667,7674767,7681867,7690967,7693967,7696967,7715177,7718177,7722277,7729277,7733377,7742477,7747477,7750577,7758577,7764677,7772777,7774777,7778777,7782877,7783877,7791977,7794977,7807087,7819187,7820287,7821287,7831387,7832387,7838387,7843487,7850587,7856587,7865687,7867687,7868687,7873787,7884887,7891987,7897987,7913197,7916197,7930397,7933397,7935397,7938397,7941497,7943497,7949497,7957597,7958597,7960697,7977797,7984897,7985897,7987897,7996997,9002009,9015109,9024209,9037309,9042409,9043409,9045409,9046409,9049409,9067609,9073709,9076709,9078709,9091909,9095909,9103019,9109019,9110119,9127219,9128219,9136319,9149419,9169619,9173719,9174719,9179719,9185819,9196919,9199919,9200029,9209029,9212129,9217129,9222229,9223229,9230329,9231329,9255529,9269629,9271729,9277729,9280829,9286829,9289829,9318139,9320239,9324239,9329239,9332339,9338339,9351539,9357539,9375739,9384839,9397939,9400049,9414149,9419149,9433349,9439349,9440449,9446449,9451549,9470749,9477749,9492949,9493949,9495949,9504059,9514159,9526259,9529259,9547459,9556559,9558559,9561659,9577759,9583859,9585859,9586859,9601069,9602069,9604069,9610169,9620269,9624269,9626269,9632369,9634369,9645469,9650569,9657569,9670769,9686869,9700079,9709079,9711179,9714179,9724279,9727279,9732379,9733379,9743479,9749479,9752579,9754579,9758579,9762679,9770779,9776779,9779779,9781879,9782879,9787879,9788879,9795979,9801089,9807089,9809089,9817189,9818189,9820289,9822289,9836389,9837389,9845489,9852589,9871789,9888889,9889889,9896989,9902099,9907099,9908099,9916199,9918199,9919199,9921299,9923299,9926299,9927299,9931399,9932399,9935399,9938399,9957599,9965699,9978799,9980899,9981899,9989899};
    int main()
    {
    int m,n,i;
    scanf("%d%d",&m,&n);
    for(i=1;i<=779;i++)
    {
    if(a[i]>=m&&a[i]<=n)printf("%d\n",a[i]);
    if(a[i]>n) return 0;
    }
    return 0;
    }

  • 0
    @ 2015-07-24 18:51:03

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 280 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 280 KiB, score = 10
    测试数据 #2: Accepted, time = 46 ms, mem = 276 KiB, score = 10
    测试数据 #3: Accepted, time = 62 ms, mem = 280 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 280 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 280 KiB, score = 10
    测试数据 #6: Accepted, time = 889 ms, mem = 280 KiB, score = 10
    测试数据 #7: Accepted, time = 717 ms, mem = 276 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 280 KiB, score = 10
    测试数据 #9: Accepted, time = 873 ms, mem = 280 KiB, score = 10
    Accepted, time = 2602 ms, mem = 280 KiB, score = 100

    #include <iostream>
    #include <stdio.h>
    #include <math.h>
    #include <string.h>
    using namespace std;
    int how;
    bool is_it(int a)
    {
    int total=0;
    int b=a;
    int c=a;
    for(total=0;b!=0;total++)b/=10;
    if(total%2==0)
    return false;
    how=total;
    int h[100];
    int jf=a%10;
    if(jf==0||jf==2||jf==4||jf==5||jf==6||jf==8)
    return false;
    memset(h,0,sizeof(h));
    for(int i=1;i<=how;i++)
    {
    h[i]=a%10;
    a/=10;
    }
    for(int i=1;i<=(how+1)/2;i++)
    {
    if(h[i]!=h[how+1-i])
    return false;
    }total=1;
    for(int i=2;i<=sqrt(c);i++)
    if(c%i==0)
    { total=0;
    break;
    }
    if(total==0)
    return false;

    return true;

    }
    int main()
    {
    int a,b;
    scanf("%d%d",&a,&b);
    int h=min(b,9989900);
    for(int i=a;i<=h;i++)
    {
    if(is_it(i)||i==11||i==5)
    printf("%d\n",i);
    }
    }

  • 0
    @ 2015-05-06 18:20:53

    注意到一个n位的数对应两个回文数:一个有2n位,另一个有2n-1位。(比如2341对应14322341和1432321,但末位为0的数如1230,无法构成回文数)所以枚举1-9999内的所有末位不为0的数,判断每个数对应的两个回文数是不是素数即可。
    (考虑到9850589这样的回文数的存在,枚举每个数时,要不停的向前添加0,直到达到4位为止)
    (另外,得到的结果不一定是排好序的,所以要排序)
    UPD:实际上这个解法是可以优化的,首先注意到2n位的回文数一定能被11整除(回文数性质),还有原来是偶数的数产生的回文数也是偶数。

    var
        m,n,i,x1,num,j:longint;
        a:array[1..100000] of longint;
        code:integer;
        s,s2:string;
    procedure swap(x,y:longint);
    var t:longint;
    begin
        t:=a[x];
        a[x]:=a[y];
        a[y]:=t;
    end;
    
    procedure qsort(l,r:longint);  //排序
    var
        i,j,x:longint;
    begin
        i:=l;j:=r;x:=a[random(r-l+1)+l];
        repeat
            while a[i]<x do inc(i);
            while a[j]>x do dec(j);
            if i<=j then begin swap(i,j);inc(i);dec(j);end;
        until i>j;
        if i<r then qsort(i,r);
        if j>l then qsort(l,j);
    end;
    function isprime(x:longint):boolean;
    var max,i:longint;
    begin
        max:=trunc(sqrt(x));
        if x=1 then exit(true);
        for i:=2 to max do
            if x mod i=0 then exit(false);
        exit(true);
    end;
    begin
        readln(m,n);
        num:=0;
        if (m<=11) and (n>=11) then begin inc(num);a[1]:=11;end;  //特判
        for i:=1 to 9999 do
        begin
            if i mod 2=0 then continue;
            str(i,s);
        repeat
                s2:='';
                for j:=1 to length(s) do
                    s2:=s2+s[length(s)-j+1];
                val(copy(s2,1,length(s2)-1)+s,x1,code);
                if (x1>=m) and (x1<=n) and isprime(x1) then begin num:=num+1;a[num]:=x1;end;
            s:='0'+s;  //添加0
        until length(s)>4;
        end;
        qsort(1,num);
        for i:=1 to num do
            writeln(a[i]);
    end.
    
    
  • 0
    @ 2014-12-06 09:57:38

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <set>
    #include <stack>
    #include <cmath>
    #include <map>
    #define MAXN 1111111
    #define MAXM 400005
    #define INF 2000000007
    #define PI acos(-1.0)
    using namespace std;
    int x, y, num;
    int a[111111];
    bool isprime(int x)
    {
    int m = (int)sqrt(x * 1.0);
    for(int i = 2; i <= m; i++)
    if(x % i == 0) return false;
    return true;
    }
    int main()
    {
    scanf("%d%d", &x, &y);
    int cnt = 0;
    a[cnt++] = 2;
    a[cnt++] = 3;
    a[cnt++] = 5;
    a[cnt++] = 7;
    a[cnt++] = 11;
    for(int i = 1; i <= 9; i += 2)
    {
    if(i == 5) continue;
    for(int j = 0; j < 10; j++)
    {
    num = i * 100 + j * 10 + i;
    if(num >= x && num <= y)
    if(isprime(num))
    a[cnt++] = num;
    }
    }
    for(int i = 1; i <= 9; i += 2)
    {
    if(i == 5) continue;
    for(int j = 0; j < 10; j++)
    for(int k = 0; k < 10; k++)
    {
    num = i * 10000 + j * 1000 + k * 100 + j * 10 + i;
    if(num >= x && num <= y)
    if(isprime(num))
    a[cnt++] = num;
    }
    }
    for(int i = 1; i <= 9; i += 2)
    {
    if(i == 5) continue;
    for(int j = 0; j < 10; j++)
    for(int k = 0; k < 10; k++)
    for(int l = 0; l < 10; l++)
    {
    num = i * 1000000 + j * 100000 + k * 10000 + l * 1000 + k * 100 + j * 10 + i;
    if(num >= x && num <= y)
    if(isprime(num))
    a[cnt++] = num;
    }
    }
    for(int i = 0; i < cnt; i++)
    if(a[i] >= x && a[i] <= y)
    printf("%d\n", a[i]);
    system("pause");
    return 0;
    }

信息

ID
1042
难度
6
分类
搜索 | 搜索与剪枝 点击显示
标签
(无)
递交数
6231
已通过
1440
通过率
23%
被复制
2
上传者