题解

96 条题解

  • 0
    @ 2016-12-20 16:56:12

    我操。。。。总以为判断素数是用高大上的方法。。。没想到直接判就好了,我智障了 这题直接递归的搜索就好了。。。。总想着打表、、、、我服了自己 啊啊啊啊 有没有人交个朋友啊。。。。刷题好无聊啊

  • 0
    @ 2016-08-22 21:06:28

    MR + DFS
    #include"stdio.h"
    #include"stdlib.h"
    typedef long long ll;
    int a[4]={2,3,5,7};
    int b[4]={1,3,7,9};

    ll mypow(ll a,ll b,ll m)
    {
    if(b==0)
    return 1;
    if(b==1)
    return a%m;
    ll temp=mypow(a,b/2,m);
    temp*=temp;
    temp%=m;
    if(b&1)
    temp*=a;
    temp%=m;
    return temp;
    }
    bool Miller_Rabbin(ll x)
    {
    if(x==2)
    return true; ///2要直接判断
    for(int i=1;i<=50;++i){
    ll a=rand()%(x-2)+2;
    if(mypow(a,x-1,x)!=1)
    return false;
    }
    return true;
    }
    int n;
    void dfs(int num,int dep)
    {
    //puts("fuck");
    if(dep==n) {printf("%d\n",num);return; } //1,,3,,,7,,9,
    for(int i=0;i<4;i++)
    if(Miller_Rabbin(num*10+b[i]))
    dfs(num*10+b[i],dep+1);
    }

    int main()
    {

    int i;
    while(scanf("%d",&n)==1)
    {
    for(i=0;i<4;i++)
    dfs(a[i],1);
    }
    return 0;
    }

  • 0
    @ 2016-08-16 12:26:05

    miller-rabin+dfs秒杀
    ```c++
    #include <bits/stdc++.h>
    using namespace std;

    #define ll long long
    ll pow(ll a, ll n, ll m)
    {
    if (n == 0) return 1%m;
    ll p = pow(a, n>>1, m);
    p = (p%m)*(p%m)%m;
    if (n&1) p = p%m*a%m;
    return p%m;
    }

    bool is_prime(ll n)
    {
    for (int i = 1; i <= 10; i++) {
    ll a = rand()%(n-1)+1;
    //cout << a << endl;
    //cout << pow(a, n-1, n) << endl;
    if (pow(a, n-1, n) != 1) return 0;
    }
    return 1;
    }

    ll table[1001], top = 0;

    void dfs(ll k, int bas)
    {
    if (bas == 1) {
    table[++top] = k;
    return;
    }
    for (int i = 1; i <= 9; i+=2)
    if(is_prime(k*10+i))
    dfs(k*10+i, bas-1);
    }

    int main()
    {
    srand(time(0));
    int n;
    cin >> n;
    dfs(2, n);
    dfs(3, n);
    dfs(5, n);
    dfs(7, n);
    sort(table+1, table+top+1);
    for (int i = 1; i <= top; i++)
    printf("%lld\n", table[i]);
    return 0;
    }
    ```

  • 0
    @ 2016-05-21 19:39:57

    #include <cstdio>
    #include <cmath>

    int n;

    int check(int x){
    int flag,i;
    flag=1;
    for(i=2;i<=sqrt(x);i++)
    if(x%i==0){
    flag=0;
    break;
    }
    return flag;
    }

    void dfs(int x,int z){ //z位
    int r;
    if(z==n){
    printf("%d\n",x);
    return;
    }
    for(int i=1;i<=9;i++){
    r=x*10+i; //最后面加一个数
    if(check(r))
    dfs(r,z+1);
    }
    }

    int main(void){
    scanf("%d",&n);
    //注意到10以内的质数为 2 3 5 7
    dfs(2,1);
    dfs(3,1);
    dfs(5,1);
    dfs(7,1);
    return 0;
    }

  • 0
    @ 2016-02-04 16:32:28

    筛法求素数+dfs

    #include <iostream>
    #include <cmath>
    using namespace std;
    int num[10];
    int n;
    bool isPrime (long a)
    {
    if (a==1)
    return 0;
    long c,i;
    double d;
    d=sqrt(a);
    c=floor(d);
    for (i=2;i<=c;i++)
    if (a%i==0)
    return 0;
    return 1;
    }
    int build (int a)
    {
    int i,ans=0,k=1;
    for (i=a;i>=1;i--)
    {
    ans+=num[i]*k;
    k*=10;
    }
    return ans;
    }
    void dfs (int a)
    {
    int i,ll;
    bool flag;
    if (a==n+1)
    {
    for (i=1;i<=n;i++)
    cout<<num[i];
    cout<<endl;
    }
    for (i=1;i<=9;i++)
    {
    num[a]=i;
    ll=build(a);
    flag=isPrime(ll);
    if (flag==1)
    dfs(a+1);
    }
    }
    int main()
    {
    cin>>n;
    dfs (1);
    return 0;
    }

  • 0
    @ 2015-10-19 13:00:04

    uses dos;
    var
    a,b,r,d:word;
    t,n,i:longint;
    c:array[1..100000000]of byte;
    function prime(n:longint):boolean;
    var
    i:longint;
    begin
    if c[n]=2 then
    exit(true)
    else
    if c[n]=1 then
    exit(false);
    for i:=2 to trunc(sqrt(n))+1 do
    if prime(i) then
    if n mod i=0 then
    begin
    c[n]:=1;
    exit(false);
    end;
    c[n]:=2;
    exit(true);
    end;
    function chk(a:longint):boolean;
    var
    i,t:longint;
    k,k2:string;
    begin
    str(a,k);
    for i:=2 to length(k) do
    begin
    val(k[i],t);
    if t mod 2=0 then
    exit(false);
    end;
    for i:=1 to length(k) do
    begin
    val(copy(k,1,i),t);
    if not prime(t) then
    exit(false);
    end;
    exit(true);
    end;
    begin
    c[1]:=1;
    c[2]:=2;
    readln(n);
    t:=1;
    for i:=2 to n do
    t:=t*10;
    i:=t+1;
    while i<=t*10-t-1 do
    begin
    if chk(i) then
    writeln(i);
    i:=i+2;
    if n>2 then
    case (i mod 100)div 10 of
    2,4,6,8,0:inc(i,10);
    end;
    if n>3 then
    case (i mod 1000)div 100 of
    2,4,6,8,0:inc(i,100);
    end;
    if n>4 then
    case (i mod 10000)div 1000 of
    2,4,6,8,0:inc(i,1000);
    end;
    if n>5 then
    case(i mod 100000)div 10000 of
    2,4,6,8,0:inc(i,10000);
    end;
    if n>6 then
    case(i mod 1000000)div 100000 of
    2,4,6,8,0:inc(i,100000);
    end;
    end;
    end.

  • 0
    @ 2015-09-14 21:40:56

    天呀

  • 0
    @ 2015-09-14 21:40:31

    a

  • 0
    @ 2015-08-03 10:49:10

    AC100题纪念。

  • 0
    @ 2015-08-02 15:47:14

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

    long a[1001];
    int su(long x)
    {
    long i;
    for (i=2;i<=floor(sqrt(x));i++)
    if (x%i==0) return 0;
    return 1;
    }

    int main()
    {
    long i,j,jj,n,k,kk,t;
    scanf("%d",&n);
    k=4;
    a[1]=2;
    a[2]=3;
    a[3]=5;
    a[4]=7;
    for (i=1;i<n;i++)
    {
    kk=k;
    for (j=1;j<=kk;j++)
    for (t=1;t<=9;t++)
    if (su(a[j]*10+t)==1)
    {
    k++;
    a[k]=a[j]*10+t;
    }
    for (j=1;j<=kk;j++) a[j]=0;
    for (j=1;j<=k-kk;j++) a[j]=a[j+kk];
    k=k-kk;
    }
    for (i=1;i<=k;i++)
    printf("%ld\n",a[i]);
    }

  • 0
    @ 2015-02-10 21:17:29

    直接递归,grow(high,ceng)表示高位为high,要变成high*10+1、high*10+2、high*10+3........
    #include<iostream>
    #include<string.h>
    #include<stdio.h>
    using namespace std;
    bool prime(int n){
    if (n == 1)return false;
    int i;
    for (i = 2; i*i <= n; i++){
    if (n%i == 0)return false;
    }
    return true;
    }
    void grow(int high, int ceng){
    int i;
    int now;
    for (i = 1; i < 10; i ++){
    now = high * 10 + i;
    if (prime(now)){
    if (ceng == 1)
    cout << now << endl;
    else
    grow(now, ceng - 1);
    }
    }
    }
    int main(){
    freopen("in.txt", "r", stdin);
    int n;
    cin >> n;
    grow(0, n);
    return 0;
    }

  • 0
    @ 2015-01-26 17:40:40

    素数筛表示很难过
    不得不递推......

    vector<int> d[10];

    bool is_prime(int k)
    {
    for(int i=2,u=(int)sqrt(k);i<=u;i++)
    if(k%i==0) return false;
    return true;
    }

    int n;

    int main()
    {
    scanf("%d",&n);

    d[0].push_back(2);
    d[0].push_back(3);
    d[0].push_back(5);
    d[0].push_back(7);

    for(int i=1;i<n;i++)
    {
    for(int j=0;j<d[i-1].size();j++)
    {
    for(int r=0;r<10;r++)
    {
    int k=d[i-1][j]*10+r;
    if(is_prime(k)) d[i].push_back(k);
    }
    }
    }

    for(int i=0;i<d[n-1].size();i++)
    printf("%d\n",d[n-1][i]);

    return 0;
    }

  • 0
    @ 2014-11-03 22:58:41

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    int a[10][50], n, sum, i = 2, j = 1, p = 1;
    bool prime(int a)
    {
    if(a == 1) return false;

    if(a!=2)
    {for(int i = 2; i * i <= a; i++) if(a % i == 0) return false;}

    return true;
    }
    bool judge(int a, int n)
    {
    for(int i = 1; i <= n; i++)
    {
    if(prime(a) == false) return false;

    a = a / 10;
    }

    return true;
    }
    int main()
    {
    scanf("%d", &n);
    memset(a, 0, sizeof(a));
    a[1][1] = 2;
    a[1][2] = 3;
    a[1][3] = 5;
    a[1][4] = 7;

    while(i <= n)
    {
    while(a[i - 1][j] != 0)
    {
    sum = a[i - 1][j] * 10 + 1;

    if(judge(sum, i) == true)
    {
    a[i][p] = sum;
    p++;
    }

    sum = a[i - 1][j] * 10 + 3;

    if(judge(sum, i) == true)
    {
    a[i][p] = sum;
    p++;
    }

    sum = a[i - 1][j] * 10 + 7;

    if(judge(sum, i) == true)
    {
    a[i][p] = sum;
    p++;
    }

    sum = a[i - 1][j] * 10 + 9;

    if(judge(sum, i) == true)
    {
    a[i][p] = sum;
    p++;
    }

    j++;
    }

    i++;
    j = 1;
    p = 1;
    }

    i = 1;

    while(a[n][i] != 0)
    {
    printf("%d\n", a[n][i]);
    i++;
    }

    return 0;
    }

  • 0
    @ 2014-09-10 23:02:03

    绝妙算法,无视时间限制
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    int a[10][50],n,sum,i=2,j=1,p=1;
    bool prime(int a)
    {
    if(a==1) return false;
    for(int i=2;i*i<=a;i++)
    if(a%i==0)
    return false;
    return true;

    }
    bool judge(int a,int n)
    {
    for(int i=1;i<=n;i++)
    {
    if(prime(a)==false) return false;
    a=a/10;
    }
    return true;

    }
    int main()
    {
    scanf("%d",&n);
    memset(a,0,sizeof(a));
    a[1][1]=2;
    a[1][2]=3;
    a[1][3]=5;
    a[1][4]=7;
    while(i<=n)
    {
    while(a[i-1][j]!=0)
    {
    sum=a[i-1][j]*10+1;
    if(judge(sum,i)==true)
    {
    a[i][p]=sum;
    p++;

    }
    sum=a[i-1][j]*10+3;
    if(judge(sum,i)==true)
    {
    a[i][p]=sum;
    p++;

    }
    sum=a[i-1][j]*10+7;
    if(judge(sum,i)==true)
    {
    a[i][p]=sum;
    p++;

    }
    sum=a[i-1][j]*10+9;
    if(judge(sum,i)==true)
    {
    a[i][p]=sum;
    p++;

    }
    j++;

    }
    i++;
    j=1;
    p=1;

    }
    i=1;
    while(a[n][i]!=0)
    {
    printf("%d\n",a[n][i]);
    i++;

    }
    return 0;
    }

  • 0
    @ 2014-09-03 22:57:17

    从第一位是质数开始枚举 然后第二位也是质数 依次类推 可以0ms秒杀

  • 0
    @ 2014-07-05 22:26:27

    ###Block code
    /*happywu
    * vijos 1359
    * 2014.7.5
    */
    #include<cstdio>
    #include<iostream>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    const int a[6]={1,2,3,5,7,9};
    int n;
    bool pd(int x)
    {
    if(x==1)return 0;
    int k=sqrt(x);
    for(int i=2;i<=k;i++)
    {
    if(x%i==0)return 0;
    }
    return 1;
    }
    void search(int now,int len)
    {
    if(len>n)
    {
    printf("%d\n",now);
    return;
    }
    int tmp=now;
    for(int i=0;i<6;i++)
    {
    tmp=now*10+a[i];
    if(pd(tmp))search(tmp,len+1);
    }
    }
    int main()
    {
    scanf("%d",&n);
    search(0,1);
    return 0;
    }

  • 0
    @ 2012-10-07 17:18:40

    5 忘加了。。。AC率。。。。AC 20题纪念

    Program p1359;

    const a:array[1..6] of integer=(1,2,3,5,7,9);

    var n,i,j:integer;

    num:longint;

    function check(num:longint):boolean;

    var i:integer;

    begin

    for i:=2 to trunc(sqrt(num)) do

    if num mod i=0 then

    begin

    check:=false;

    exit;

    end;

    if num=1 then begin check:=false;exit;end;

    check:=true;

    end;

    procedure find(num:longint;l:integer);

    var i:integer;

    begin

    if not check(num) then exit;

    if l=n then begin

    writeln(num);

    exit;

    end;

    for i:=1 to 6 do find(num*10+a[i],l+1);

    end;

    begin

    readln(n);

    find(0,0);

    end.

  • 0
    @ 2012-08-27 13:07:41

    var n:longint;

      s:string;

    function zs(k:longint):boolean;

    var j:longint;

    begin

    zs:=true;

    if k=1 then begin zs:=false; exit; end;

    for j:=2 to round(sqrt(k)) do

    if k mod j =0 then

    begin

    zs:=false;

    exit;

    end;

    end;

    procedure find(m:integer);

    var i,x,t,p:longint;

    begin

    if m>n then begin writeln(s); exit; end;

    for i:=1 to 9 do

    begin

    t:=0;

    p:=1;

    for x:=m-1 downto 1 do

    begin

    p:=p*10;

    t:=(ord(s[x])-48)*p+t;

    end;

    t:=t+i;

    if zs(t) then

    begin

    insert(chr(i+48),s,m);

    find(m+1);

    delete(s,m,1);

    end;

    end;

    end;

    begin

    readln(n);

    find(1);

    end.

    超正常!!!!!!!!!!!

  • 0
    @ 2010-04-11 21:54:39

    打表才是王道

    0msAC

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    贴下

    #include

    int main(void)

    {

    int n;

    long min=1;

    long max=1;

    int i=0;

    static long a[150]={2,3,5,7,23,29,31,37,53,59,71,73,79,233,239,293,311,313,317,373,379,59

    3,599,719,733,739,797,2333,2339,2393,2399,2939,3119,3137,3733,3739

    ,3793,3797,5939,7193,7331,7333,7393,23333,23339,23399,23993,29399

    ,31193,31379,37337,37339,37397,59393,59399,71933,73331,73939,233

    993,239933,293999,373379,373393,593933,593993,719333,739391,739

    393,739397,739399,2339933,2399333,2939999,3733799,5939333,7393

    913,7393931,7393933,23399339,29399999,37337999,59393339,739391

    33};

    scanf("%d",&n);

    for(i=1;i=min&&a[i]

  • 0
    @ 2010-04-07 18:35:03

    const

    a:array[1..4]of integer=(1,3,7,9);

    s:array[1..4]of integer=(2,3,5,7);

    var n,i:longint;

    procedure dfs(i,len:longint);

    var j:integer;

    begin

    for j:=2 to trunc(sqrt(i)) do

    if i mod j=0 then exit;

    if len=n then begin writeln(i);exit;end;

    for j:=1 to 4 do dfs(i*10+a[j],len+1);

    end;

    begin

    readln(n);

    for i:=1 to 4 do dfs(s[i],1);

    end.

信息

ID
1359
难度
3
分类
搜索 | 枚举数论 点击显示
标签
(无)
递交数
2004
已通过
953
通过率
48%
被复制
7
上传者