Hướng dẫn giải của Vòng số nguyên tố
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const max=10000; re:array[1..9] of longint=(1,2,2,4,96,1024,2880,81024,770144); var n:byte; dem:longint; a,t:array[1..20] of byte; d:array[2..20] of byte; prime:array[2..39] of byte; procedure init; var i,j:byte; begin fillchar(prime,sizeof(prime),0); for i:=2 to 37 do if prime[i]=0 then begin j:=2*i; while j<=39 do begin prime[j]:=1; j:=j+i; end; end; end; procedure rf; begin read(n); end; procedure att(i:byte); var j,k:byte; begin for j:=2 to 2*n do begin if (d[j]=0) and (prime[j+a[i-1]]=0) then begin a[i]:=j; d[j]:=1; if i<2*n then att(i+1) else begin if prime[a[i]+1]=0 then begin for k:=1 to 2*n do write(a[k],' '); writeln; inc(dem); if dem>max then break; end; end; a[i]:=0; d[j]:=0; end; end; end; procedure pr; var i,j:byte; begin writeln(re[n]); fillchar(a,sizeof(a),0); fillchar(d,sizeof(d),0); init; dem:=1; a[1]:=1; att(2); end; begin rf; pr; end.
Code mẫu của happyboy99x
#include <cstdio> #define FOR(i, a, b) for( int i = (a), _b = (b); i <= _b; ++i ) #define REP(i, n) for( int i = 0, _n = (n); i < _n; ++i ) int n, pr[40], res[25], ch[40]; int tp[10005][25], count; void eratos( int n ) { REP(i, n+1) pr[i] = 1; pr[0] = pr[1] = 0; int i = 2; while ( i * i <= n ) { for( int j = i + i; j <= n; j += i ) pr[j] = 0; do ++i; while( i * i <= n && !pr[i] ); } } void backtrack( int k ) { if ( k == 2*n ) { if (pr[res[k-1] + res[0]]) { if ( count < 10000 ) REP(i, k) tp[count][i] = res[i]; count++; } } else FOR(i, 1, 2*n) if ( !ch[i] && pr[res[k-1]+i] ) { res[k] = i; ch[i] = 1; backtrack(k+1); ch[i] = 0; } } int main() { eratos(39); scanf( "%d", &n ); res[0] = 1; ch[1] = 1; count = 0; backtrack(1); printf( "%d\n", count ); REP(i, count < 10000 ? count : 10000) { printf( "%d", tp[i][0] ); FOR(j, 1, 2*n-1) printf( " %d", tp[i][j] ); putchar('\n'); } return 0; }
Code mẫu của ladpro98
program pcircle; uses math; const a :array[1..9] of longint = (1,2,2,4,96,1024,2880,81024,770144); var res:array[1..20] of longint; check:array[1..20] of boolean; n,k:longint; done:boolean; function isPrime(x:longint):boolean; var k,n:longint; begin n:=x; if (n=2) or (n=3) or (n=5) or (n=7) then exit(true); if n mod 2 = 0 then exit(false); if (n mod 3 = 0) then exit(false); k:=0; while k<=trunc(sqrt(n)) do begin inc(k,6); if (n mod (k-1) = 0 ) or (n mod (k+1) = 0) then exit(false); end; isPrime:=true; end; procedure print; var i:longint; begin for i:=1 to n do write(res[i],' '); writeln; end; procedure back(i,val:longint); var j:longint; begin if done then exit; if i>n then begin if (isprime(val+res[1])) then begin inc(k); if k>10000 then done:=true else print; end; exit; end; for j:=1 to n do if (not check[j]) and isprime(val+j) then begin check[j]:=true; res[i]:=j; back(i+1,j); check[j]:=false; end; end; begin readln(n); fillchar(check,sizeof(check),false); k:=0; n:=2*n; res[1]:=1; check[1]:=true; writeln(a[n div 2]); back(2,1); end.
Code mẫu của RR
const res:array[2..9] of longint=(2,2,4,96,1024,2880,81024,770144); var used,p:array[1..40] of boolean; a:array[1..40] of longint; cnt,n,i:longint; function isPrime(n:longint):boolean; var i:longint; begin for i:=2 to trunc(sqrt(n)) do if n mod i=0 then exit(false); exit(i>1); end; procedure dequy(i:longint); var j,k:longint; begin if cnt>10000 then exit; for j:=2 to n shl 1 do if (not used[j]) and p[a[i-1]+j] then begin used[j]:=true; a[i]:=j; if i<n shl 1 then dequy(i+1) else if p[a[1]+a[i]] then begin inc(cnt); if cnt>10000 then exit; for k:=1 to n shl 1 do write(a[k],' '); writeln; end; used[j]:=false; if cnt>10000 then exit; end; end; begin fillchar(used,sizeof(used),false); for i:=1 to 40 do p[i]:=isPrime(i); a[1]:=1; used[1]:=true; read(n); writeln(res[n]); dequy(2); end.
Code mẫu của ll931110
Program PCIRCLE; Const input = ''; output = ''; Var a: array[1..20] of integer; free,p: array[1..40] of boolean; pnum: array[2..9] of longint; n,c,num: longint; fo: text; Procedure init; Var fi: text; Begin Assign(fi, input); Reset(fi); Readln(fi, n); Close(fi); c:= n * 2; Fillchar(free, sizeof(free), true); a[1]:= 1; num:= 0; End; Procedure printresult; Var i: integer; Begin For i:= 1 to c do write(fo, a[i], ' '); Writeln(fo); End; Procedure primearray; Begin Fillchar(p, sizeof(p), false); p[2]:= true; p[17]:= true; p[3]:= true; p[19]:= true; p[5]:= true; p[23]:= true; p[7]:= true; p[29]:= true; p[11]:= true; p[31]:= true; p[13]:= true; End; Procedure pnumber; Begin pnum[2]:= 2; pnum[3]:= 2; pnum[4]:= 4; pnum[5]:= 96; pnum[6]:= 1024; pnum[7]:= 2880; pnum[8]:= 81024; pnum[9]:= 770144; End; Procedure attempt(t: integer); Var i: integer; Begin For i:= 2 to c do If free[i] and p[i + a[t - 1]] then Begin a[t]:= i; free[i]:= false; If (t = c) and p[a[c] + a[1]] then Begin inc(num); If num <= 10000 then printresult else exit; End else attempt(t + 1); free[i]:= true; End; End; Begin init; primearray; Assign(fo, output); Rewrite(fo); pnumber; Writeln(fo, pnum[n]); attempt(2); Close(fo); End.
Code mẫu của khuc_tuan
#include "iostream" #include "stdio.h" using namespace std; int n; int a[22]; bool ngto[100]; bool dd[100]; int socach; void duyet(int i, bool in) { if(in && socach>=10000) return; if(i==2*n) { if(ngto[a[2*n-1]+a[0]]) { ++socach; if(in && socach<=10000) { for(int i=0;i<2*n;++i) printf("%d ",a[i]); printf("\n"); } } return; } for(int x=1;x<=2*n;++x) if(ngto[x+a[i-1]] && !dd[x]) { dd[x] = true; a[i] = x; duyet(i+1,in); dd[x] = false; } } void init() { memset( ngto, true, sizeof(ngto)); ngto[0] = ngto[1] = false; for(int i=2;i<100;++i) { if(ngto[i]) { for(int j=i+i;j<100;j+=i) ngto[j] = false; } } } int main() { scanf("%d",&n); a[0] = 1; dd[1] = true; init(); duyet(1, false); printf("%d\n", socach); socach = 0; duyet(1, true); return 0; }
Bình luận