专栏首页饶文津的专栏【USACO 1.5】Prime Palindromes

【USACO 1.5】Prime Palindromes

 1 /*
 2 TASK: pprime
 3 LANG: C++
 4 SOLVE: 枚举数的长度,dfs出对称的数,判断是否在范围内,是否是素数
 5 原来想着枚举每个范围里的数,但是显然超时,范围最大是10^9。
 6 对称的数只有9*2+9*9*2+9*9*9*2+9*9*9*9*2个,再加上几个九位数的。
 7 共一万多个。
 8 n=10000
 9 复杂度就是O(根号n)。
10  */
11 #include<cstdio>
12 #include<cstring>
13 int l,r,ans;
14 bool is_prime(int x){
15     for(int i=2;i<=x/i;i++)
16         if(x%i==0)return 0;
17     return 1;
18 }
19 void dfs(char* s,int d,int len){
20     if(d==(len+1)/2){
21         int x;
22         sscanf(s,"%d",&x);
23         if(x>=l&&x<=r&&is_prime(x))
24             printf("%d\n",x);
25         return;
26     }
27     for(int i=(d==0);i<=9;i++){
28         s[d]=s[len-1-d]=i+'0';
29         dfs(s,d+1,len);
30     }
31 }
32 void solve(){
33     char s[12];
34     for(int len=1;len<9;len++){
35         memset(s,0,sizeof s);
36         dfs(s,0,len);
37     }
38 }
39 int main(){
40     freopen("pprime.in","r",stdin);
41     freopen("pprime.out","w",stdout);
42     scanf("%d%d",&l,&r);
43     solve();
44     return 0;
45 }
46   

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 弱校联盟10.3

    n对括号最多需要1+2+..+n次交换,当它是)))..(((的形式时,)))(((需要6次,然后把中间两个交换一下,))()((就还需要5次,再交换一次靠近左...

    饶文津
  • 【POJ 3062】Party(2-SAT、tarjan)

    a,a',b,b'分别表示两对夫妇,如果a,b有矛盾,那么a要来,就只能来b',b要来,就只能来a'。于是建了两条边(a,b'),(b,a')。

    饶文津
  • 【USACO 3.2】Magic Squares

    4*2个格子分别为 1234 8765 的魔板有3种操作,A:上下两排互换,B:最后一列放到第一列前面,C:中间四个顺时针旋转1格。 现在给出目标状态,...

    饶文津
  • String Problem(KMP+最小表示法)- HDU 3374

    Give you a string with length N, you can generate N strings by left shifts. For ...

    ACM算法日常
  • c++之函数模板案例

    绝命生
  • c++ LeetCode (初级字符串篇) 九道算法例题代码详解(二)

    原文链接:https://www.cnblogs.com/DOMLX/p/11089327.html

    徐飞机
  • ZOJ 3490 String Successor(模拟)

    Time Limit: 2 Seconds Memory Limit: 65536 KB The successor to a string ca...

    ShenduCC
  • 历届试题 分糖果

      有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果,然后进行下面的游戏: 每个小朋友都把自己的糖果分一半给左手边的孩子。   一轮分糖后,拥有...

    刘开心_1266679
  • 颜色聚合向量

    package com.imageretrieval.features; /** * 颜色聚合向量<br> * 参考链接:http://www.docin...

    Venyo
  • 桶排序的算法

    思路:设数组的长度为len,创建三个长度为len+1的(桶)数组。将数组的元素根据大小放在不同的桶中,其中,必定有差值大于一个桶的差存在,故同一个桶中不可能出现...

    曼路

扫码关注云+社区

领取腾讯云代金券