Java 解法, 执行用时: 1179ms, 内存消耗: 29100K, 提交时间: 2023-03-23 21:29:31
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.*;
public class Main {
static class Task {
long f[] = new long[340000];
long g[] = new long[340000];
void init(){
long i,j,m;
for(m=1;m<=nn/m;++m)f[(int)m]=nn/m-1;
for(i=1;i<=m;++i)g[(int)i]=i-1;
for(i=2;i<=m;++i){
if(g[(int)i]==g[(int)(i-1)])continue;
for(j=1;j<=Math.min(m-1,nn/i/i);++j){
if(i*j<m)f[(int)j]-=f[(int)(i*j)]-g[(int)(i-1)];
else f[(int)j]-=g[(int)(nn/i/j)]-g[(int)(i-1)];
}
for(j=m;j/i>=i;--j)g[(int)j]-=g[(int)(j/i)]-g[(int)(i-1)];
}
}
long nn;
int a[][] = new int[5][5];
void tian(int num,int line){
int x= 4;
while(num>0){
int d = num % 10;
a[line][x--] =d;
num /= 10;
}
}
void tian1(int num,int col){
int x = 4;
while(num>0){
int d = num % 10;
a[x--][col] = d;
num /= 10;
}
}
Map<Integer,List<Integer> > mp1 = new HashMap<>();
List<String> li11 = new ArrayList<>();
boolean ck(int a[][]) {
for (int i = 1; i <= 4; ++i) {
int num = 0;
for (int h = 0; h <= 4; ++h) {
num = num * 10 + a[i][h];
}
if (!good[num]) {
return false;
}
}
for (int i = 1; i <= 4; ++i) {
int num = 0;
for (int h = 0; h <= 4; ++h) {
num = num * 10 + a[h][i];
}
if (!good[num]) {
return false;
}
}
return true;
}
boolean visit[] = new boolean[100000 + 1];
boolean good[] = new boolean[100000 + 1];
public void solve(int testNumber, InputReader in, PrintWriter out) {
int sum = in.nextInt();
int num = in.nextInt();
int maxn = 100000;
int prime[] = new int[maxn + 1];
visit[1] = true;
int p = 0;
List<Integer> li = new ArrayList<>();
for (int i = 2; i <= maxn; ++i) {
if (!visit[i]) {
prime[p++] = i;
// prime
if(i>9999&&i<=99999){
int s = 0;
int ii = i;
while(ii>0){
s += ii % 10;
ii /= 10;
}
if(s==sum) {
int d = (i/10000)%10;
List<Integer> lis = mp1.getOrDefault(d, new ArrayList<>());
lis.add(i);
mp1.put(d,lis);
good[i] = true;
}
}
}
for (int j = 0; j < p; ++j) {
int check = i * prime[j];
if( check > maxn){
break;
}
visit[check] = true;
if (i % prime[j] == 0) {
break;
}
}
}
List<Integer> first = mp1.get(num);
outer: for(int u: first){
tian(u,0);
for(int i=0;i<=4;++i){
if(a[0][i]==0){
continue outer;
}
}
outer1: for(int v: first) {
tian1(v, 0);
for(int i=0;i<=4;++i){
if(a[i][0]==0){
continue outer1;
}
}
for(int w: first) {
for(int i=4;i>=0;--i){
a[i][i] = w%10;
w /= 10;
}
for(int t1=0;t1<=9;++t1){
int t2 = sum - a[4][0] -a[2][2] -a[0][4] - t1;
if(t2<0||t2>9) continue;
int vv = a[4][0]*10000 + t1*1000 + a[2][2]*100 + t2*10 + a[0][4];
if(good[vv]) {
a[3][1] = t1;
a[1][3] = t2;
for(int y1=0;y1<=9;++y1){
int y2 = sum - a[1][0] -a[1][1] -a[1][3] - y1;
if(y2<0||y2>9) continue;
int yy = a[1][0]*10000 + a[1][1]*1000 + y1*100 + a[1][3]*10 + y2;
if(!good[yy]) { continue ;}
a[1][2] = y1;
a[1][4] = y2;
for(int y3=0;y3<=9;++y3) {
int y4 = sum - a[0][1] - a[1][1] - a[3][1]- y3;
if (y4 < 0 || y4 > 9) continue;
int yyy = a[0][1] * 10000 + a[1][1] * 1000 + y3 * 100 + a[3][1] * 10 + y4;
if (!good[yyy]) {
continue;
}
a[2][1] = y3;
a[4][1] = y4;
for(int y5 = 0; y5<= 9 ;++y5){
int y6 = sum - a[0][4] - a[1][4] - y5 -a[4][4];
if(y6<0||y6>9) continue;
a[2][4] = y5;
a[3][4] = y6;
int y7 = sum - a[2][0] - a[2][1] - a[2][2] - y5;
if(y7<0||y7>9) continue;
a[2][3] = y7;
int y8 = sum - a[3][0] - a[3][1] - a[3][3] - y6;
if(y8<0||y8>9) continue;
a[3][2] = y8;
int y9 = sum - a[0][2] - a[1][2] - a[2][2] - a[3][2];
if(y9<0||y9>9) continue;
a[4][2] = y9;
int y10 = sum - a[0][3] - a[1][3] - a[2][3] - a[3][3];
if(y10<0||y10>9) continue;
a[4][3] = y10;
if(ck(a)){
StringBuilder sb = new StringBuilder();
for (int i = 0; i <= 4; ++i) {
for (int h = 0; h <= 4; ++h) {
sb.append(a[i][h]);
}
sb.append('\n');
}
li11.add(sb.toString());
}
}
}
}
}
}
}
}
}
Collections.sort(li11,(x,y)->{
return x.compareTo(y);
});
for(String res:li11){
out.println(res);
}
}
public void solve111(int testNumber, InputReader in, PrintWriter out) {
int n = in.nextInt();
m = in.nextInt();
double c[][] = new double[n][m];
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
c[i][j] = in.nextInt();
}
}
int cost[] = new int[n];
for(int i=0;i<n;++i){
cost[i] = in.nextInt();
}
Integer arr[] = new Integer[n];
for(int i=0;i<n;++i){
arr[i] = i;
}
int num = 0;
Arrays.sort(arr, (x,y)->{
return cost[x] - cost[y];
});
long s = 0;
boolean used[] = new boolean[n];
for(int j=0;j<m;++j){
for(int h = 0; h < n;++h){
int idx = arr[h];
if(used[idx]) continue;
if(Math.abs(c[idx][j])>0.01) {
used[idx] = true;
s += cost[idx];
num++;
for (int hh = 0; hh < n; ++hh) {
if (hh == h) continue;
int idx1 = arr[hh];
if (Math.abs(c[idx1][j])>0.01) {
double k = c[idx1][j] / c[idx][j];
for(int i = j; i< m;++i){
c[idx1][i] -= k * c[idx][i];
}
}
}
}
}
}
out.println(num + " " + s);
}
public double[][] gauss(double a[][]){
int n = a.length;
int m = n+1;
for(int j=0;j<n;++j){
int idx = j; double ck = a[idx][j];
for(int i=j+1;i<n;++i){
if( Math.abs(a[i][j]) > ck ){
ck = Math.abs(a[i][j]);
idx = i;
}
}
if(idx!=j) {
double cg[] = a[j];
a[j] = a[idx];
a[idx] = cg;
}
for(int i=0;i<n;++i){
if(i==j) continue;
double rate = a[i][j] / a[j][j];
for(int k=j;k<m;++k){
a[i][k] -= rate * a[j][k];
}
}
}
return a;
}
public int num(int i,int j){
return i*m + j;
}
String cs[];
String ops[];
public void solve22(int testNumber, InputReader in, PrintWriter out) {
n = in.nextInt();
m = in.nextInt();
int t = in.nextInt();
int act = in.nextInt();
cs = new String[n];
for(int i=0;i<n;++i){
cs[i] = in.next();
}
ops = new String[act];
for(int i=0;i<act;++i){
ops[i] = in.next();
}
long v[][] = new long[1][n*m+1];
v[0][n*m] = 1;
int q = t/60;
int r = t%60;
long ju1[][] = go(60);
long ju2[][] = go(r);
long res[][] = quick(ju1,q);
res = mult(res,ju2);
res = mult(v,res);
long big = 0;
for(int i=0;i<=n*m;++i){
big = Math.max(big, res[0][i]);
}
out.println(big);
}
long[][] mult(long a[][],long b[][]){
int l1 = a.length;
int l2 = b.length;
int l3 = b[0].length;
long r[][] = new long[l1][l3];
for(int i=0;i<l1;++i){
for(int j=0;j<l2;++j){
for(int k=0;k<l3;++k){
r[i][k] = r[i][k] + a[i][j] * b[j][k];
}
}
}
return r;
}
long[][] add(long a[][],long b[][],long mod){
int l1 = a.length;
int l2 = a[0].length;
long r[][] = new long[l1][l2];
for(int i=0;i<l1;++i){
for(int j=0;j<l2;++j){
r[i][j] = (a[i][j] + b[i][j])%mod;
}
}
return r;
}
long[][] ones(int len){
long r[][] = new long[len][len];
for(int i=0;i<len;++i){
r[i][i] = 1L;
}
return r;
}
long[][] quick(long a[][], int times){
int len = a.length;
long ans[][] = ones(len);
while(times>0){
if((times&1)==1) {
ans = mult(ans, a);
}
a = mult(a, a);
times >>= 1;
}
return ans;
}
public long[][] go(int tm){
int len = n*m+1;
long t[][] = new long[len][len];
for(int i=0;i<len;++i){
t[i][i] = 1;
}
for(int c=0;c<tm;++c){
long dt[][] = new long[len][len];
dt[len-1][len-1] = 1;
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
int op = cs[i].charAt(j) - '0';
String cur = ops[op];
int l = cur.length();
int idx = c%l;
char p = cur.charAt(idx);
if(p=='D'){
}else if(p=='N'){
if(i>0) {
dt[num(i, j)][num(i - 1, j)] = 1;
}
}else if(p=='S'){
if(i+1<n) {
dt[num(i, j)][num(i + 1, j)] = 1;
}
}else if(p=='W'){
if(j-1>=0) {
dt[num(i, j)][num(i , j - 1)] = 1;
}
}else if(p=='E'){
if(j+1<m) {
dt[num(i, j)][num(i , j + 1)] = 1;
}
}else{
dt[num(i , j )][num(i , j )] = 1;
dt[len-1][num(i , j )] = p-'0';
}
}
}
t = mult(t, dt);
}
return t;
}
boolean ck(int x,int y){
return x >= 0 && x < n && y >=0 && y< m && mp[x][y]=='.';
}
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int bfs2(int fx,int fy, int tx,int ty,int x1,int y1){
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[]{fx,fy});
int dp[][] = new int[n][m];
for(int i=0;i<n;++i){
Arrays.fill(dp,100000000);
}
dp[fx][fy] = 0;
while(q.size()>0){
int c[] = q.poll();
for(int j=0;j<4;++j){
int nx = c[0] + dx[j];
int ny = c[1] + dy[j];
if(ck(nx,ny) && !(nx==x1&&ny==y1)){
}
}
}
return -1;
}
List<Integer> steps = new ArrayList<>();
int bfs1(){
for(int j=0;j<4;++j){
int rx = bx + dx[j];
int ry = by + dy[j];
int tuix = bx - dx[j];
int tuiy = by - dy[j];
if(ck(rx,ry) && ck(tuix,tuiy)){
steps.clear();
}
}
Queue<int[]> q =new ArrayDeque<>();
q.offer(null);
return -1;
}
int mx,my,bx,by,tx,ty,n,m;
char mp[][];
public void solve1(int testNumber, InputReader in, PrintWriter out) {
int t = 1;
while(true){
n = in.nextInt();
m = in.nextInt();
if(n==0&&m==0) break;
out.println("Maze #"+ t);
mp = new char[n][m];
for(int i=0;i<n;++i){
mp[i] = in.next().toCharArray();
for(int j=0;j<m;++j){
if(mp[i][j]=='S'){
mx = i;my = j; mp[i][j] = '.';
}else if(mp[i][j]=='B'){
bx = i;by = j; mp[i][j] = '.';
}else if(mp[i][j]=='T'){
tx = i;ty = j; mp[i][j] = '.';
}
}
}
out.println(bfs1());
}
}
}
public static String roundS(double result, int scale){
String fmt = String.format("%%.%df", scale);
return String.format(fmt, result);
// DecimalFormat df = new DecimalFormat("0.000000");
// double result = Double.parseDouble(df.format(result));
}
private static void sort(double[] arr) {
Double[] objArr = Arrays.stream(arr).boxed().toArray(Double[]::new);
Arrays.sort(objArr);
for (int i = 0; i < arr.length; i++) {
arr[i] = objArr[i];
}
}
private static void sort(int[] arr) {
Integer[] objArr = Arrays.stream(arr).boxed().toArray(Integer[]::new);
Arrays.sort(objArr);
for (int i = 0; i < arr.length; i++) {
arr[i] = objArr[i];
}
}
private static void sort(long[] arr) {
Long[] objArr = Arrays.stream(arr).boxed().toArray(Long[]::new);
Arrays.sort(objArr);
for (int i = 0; i < arr.length; i++) {
arr[i] = objArr[i];
}
}
private static void solve() {
InputStream inputStream = System.in;
//InputStream inputStream = new FileInputStream(new File("D:\\chrome_download\\travel1.in"));
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task task = new Task();
task.solve(1, in, out);
out.close();
}
public static void main(String[] args) {
//new Thread(null, () -> solve(), "1", 1 << 20).start();
solve();
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String nextLine() {
String line = null;
try {
line = reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
return line;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public char nextChar() {
return next().charAt(0);
}
public int[] nextArray(int n) {
int res[] = new int[n];
for (int i = 0; i < n; ++i) {
res[i] = nextInt();
}
return res;
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
}
C++14(g++5.4) 解法, 执行用时: 15ms, 内存消耗: 632K, 提交时间: 2020-07-22 11:55:09
#include<cstdio>
#include<cstring>
#include<bitset>
#include<algorithm>
const int n=5;
typedef unsigned char byte;
typedef struct _dmat{int val[n];} dmat;
const byte nil=10;
int p[100000];
bool q[100000];
int sum,a00,cnt=0;
byte a[5][5];
dmat ans[1000];
bool valid[11][11][11][11][11];
const int x[25]={0,0,1,2,3,4,4,4,4,4,1,2,3,3,1,1,1,3,3,2,2,2,0,0,0};
const int y[25]={0,4,4,4,4,4,0,1,2,3,1,2,3,1,3,0,2,0,2,0,1,3,1,2,3};
inline int get_num(byte x[]){return 10000*x[0]+1000*x[1]+100*x[2]+10*x[3]+x[4];}
inline int digit_sum(int x) {register int res=0;for(;x;res+=x%10,x/=10);return res;}
inline bool cmp(const dmat &u,const dmat &v) {
for(int i=0;i<n;i++)if(u.val[i]!=v.val[i])return u.val[i]<v.val[i];
return false;
}
bool check(){
for(int i=0;i<5;i++) {
if(!valid[a[i][0]][a[i][1]][a[i][2]][a[i][3]][a[i][4]])return false;
if(!valid[a[0][i]][a[1][i]][a[2][i]][a[3][i]][a[4][i]])return false;
}
if(!valid[a[0][0]][a[1][1]][a[2][2]][a[3][3]][a[4][4]])return false;
if(!valid[a[4][0]][a[3][1]][a[2][2]][a[1][3]][a[0][4]])return false;
return true;
}
void dfs(int k){
if(!check())return;
if(k==25){
for(int i=0;i<n;i++)ans[cnt].val[i]=get_num(a[i]);
cnt++;
return;
}
for(int i=0+(int)(x[k]==0||y[k]==0);i<10;i++){
a[x[k]][y[k]]=i;
dfs(k+1);
a[x[k]][y[k]]=nil;
}
}
void init(){
valid[nil][nil][nil][nil][nil]=true;
memset(a,nil,sizeof a);
a[0][0]=a00;
for(int i=2;i<100000;i++){
if(!q[i]){
p[++p[0]]=i;
if(i>=10000 && digit_sum(i)==sum){
byte t[]={byte(i/10000),byte(i/1000%10),byte(i/100%10),byte(i/10%10),byte(i%10)};
for(int i=1;i<32;i++){
std::bitset<n> j(i);
valid[j[0]?t[0]:nil][j[1]?t[1]:nil][j[2]?t[2]:nil][j[3]?t[3]:nil][j[4]?t[4]:nil]=true;
}
}
}
for(int j=1;j<=p[0] && i*p[j]<100000;j++){
q[i*p[j]]=true;
if(i%p[j]==0)break;
}
}
}
void output(int k) {
for(int i=0;i<n;i++)printf("%d\n",ans[k].val[i]);
}
int main(){
scanf("%d%d",&sum,&a00);
if(sum<7||sum>45){printf("NONE\n");return 0;}
if(sum%2==0){printf("NONE\n");return 0;}
if(sum%3==0){printf("NONE\n");return 0;}
init();
if(a00)dfs(1);
if(cnt==0){printf("NONE\n");return 0;}
std::sort(ans,ans+cnt,cmp);
for(int i=0;i<cnt;i++){if(i)printf("\n");output(i);}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 19ms, 内存消耗: 664K, 提交时间: 2020-07-21 23:33:13
#include<cstdio>
#include<cstring>
#include<bitset>
#include<algorithm>
const int n=5;
typedef unsigned char byte;
typedef byte d1n[n];
typedef d1n dnn[n];
typedef struct _dmat{int val[n];} dmat;
const byte nil=10;
int p[100000];
bool q[100000];
int sum,a00,cnt=0;
dnn a;
dmat ans[1000];
bool valid[11][11][11][11][11];
const int x[25]={0,0,1,2,3,4,4,4,4,4,1,2,3,3,1,1,1,3,3,2,2,2,0,0,0};
const int y[25]={0,4,4,4,4,4,0,1,2,3,1,2,3,1,3,0,2,0,2,0,1,3,1,2,3};
inline int get_num(d1n x){return 10000*x[0]+1000*x[1]+100*x[2]+10*x[3]+x[4];}
inline int digit_sum(int x) {register int res=0;for(;x;res+=x%10,x/=10);return res;}
inline bool cmp(const dmat &u,const dmat &v) {
for(int i=0;i<n;i++)if(u.val[i]!=v.val[i])return u.val[i]<v.val[i];
return false;
}
bool check(){
if(!valid[a[0][0]][a[1][1]][a[2][2]][a[3][3]][a[4][4]])return false;
if(!valid[a[4][0]][a[3][1]][a[2][2]][a[1][3]][a[0][4]])return false;
for(int i=0;i<5;i++) {
if(!valid[a[i][0]][a[i][1]][a[i][2]][a[i][3]][a[i][4]])return false;
if(!valid[a[0][i]][a[1][i]][a[2][i]][a[3][i]][a[4][i]])return false;
}
return true;
}
void dfs(int k){
if(!check())return;
if(k==25){
for(int i=0;i<n;i++)ans[cnt].val[i]=get_num(a[i]);
cnt++;
return;
}
for(int i=0+(int)(x[k]==0||y[k]==0);i<10;i++){
a[x[k]][y[k]]=i;
dfs(k+1);
a[x[k]][y[k]]=nil;
}
}
void init(){
valid[nil][nil][nil][nil][nil]=true;
memset(a,nil,sizeof a);
a[0][0]=a00;
for(int i=2;i<100000;i++){
if(!q[i]){
p[++p[0]]=i;
if(i>=10000 && digit_sum(i)==sum){
d1n t={byte(i/10000),byte(i/1000%10),byte(i/100%10),byte(i/10%10),byte(i%10)};
for(int i=1;i<32;i++){
std::bitset<n> j(i);
valid[j[0]?t[0]:nil][j[1]?t[1]:nil][j[2]?t[2]:nil][j[3]?t[3]:nil][j[4]?t[4]:nil]=true;
}
}
}
for(int j=1;j<=p[0] && i*p[j]<100000;j++){
q[i*p[j]]=true;
if(i%p[j]==0)break;
}
}
}
void output(int k) {
for(int i=0;i<n;i++)printf("%d\n",ans[k].val[i]);
}
int main(){
scanf("%d%d",&sum,&a00);
init();
if(a00)dfs(1);
if(cnt==0){printf("NONE\n");return 0;}
std::sort(ans,ans+cnt,cmp);
for(int i=0;i<cnt;i++){if(i)printf("\n");output(i);}
return 0;
}
的方阵，每行、每列、两条对角线上的数字可以看作是五位的素数。方格中的行按照从左到右的顺序组成一个素数，而列按照从上到下的顺序。两条对角线也是按照从左到右的顺序来组成。这些素数每一位上的数之和必须相等。左上角的数字是预先定好的。一个素数可能在方阵中重复多次。不计含有前导0的五位素数，如00003不是五位素数。
给出每一位上的数之和，以及左上角的数字，请输出方阵所有可能的填数方案。如果不只有一个解，将它们全部输出（按照这25个数字组成的25位数的大小排序）。