首页 > 试题广场 >

星际密码

[编程题]星际密码

热度指数：5557 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

星际战争开展了100年之后，NowCoder终于破译了外星人的密码！他们的密码是一串整数，通过一张表里的信息映射成最终4位密码。表的规则是：n对应的值是矩阵X的n次方的左上角，如果这个数不足4位则用0填充，如果大于4位的则只输出最后4位。
|1 1|^n => |Xn ..|
|1 0| |.. ..|
例如n=2时，
|1 1|^2 => |1 1| * |1 1| => |2 1|
|1 0| |1 0| |1 0| |1 1|
即2对应的数是“0002”。

输入描述:

输入有多组数据。
每组数据两行：第一行包含一个整数n (1≤n≤100)；第二行包含n个正整数Xi (1≤Xi≤10000)

输出描述:

对应每一组输入，输出一行相应的密码。

示例1

输入

6
18 15 21 13 25 27
5
1 10 100 1000 10000

输出

418109877711037713937811
00010089410135017501

算法知识视频讲解

Java

来学习的小张

import java.util.*;
public class Main{
    public static void main(String[] args){
        int[] arr = new int[10001];
        arr[1] = 1;
        arr[2] = 2;
        for(int i = 3;i < 10001;i++){
            arr[i] = arr[i - 1] + arr[i - 2];
             arr[i] =  arr[i] % 10000;
        }
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            StringBuffer sb = new StringBuffer();
            int n = sc.nextInt();
            for(int i = 0;i < n;i++){
                int x = sc.nextInt();
                sb.append(String.format("%04d",arr[x]));
            }
            System.out.println(sb);
        }
        
    }    
}

发表于 2022-04-27 09:39:19 回复(0)

Java

Ash

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		int[] fib = new int[10001];
		fib[0] = 1;
		fib[1] = 1;
		// 如果这个数不足4位则用0填充，如果大于4位的则只输出最后4位。
		for (int i = 2; i < fib.length; i++) {
			fib[i] = (fib[i - 1] + fib[i - 2]) % 10000;
		}
		Scanner in = new Scanner(System.in);
		int n, x;
		n = in.nextInt();
		while (in.hasNextInt()) {
			while (n-- > 0) {
				x = in.nextInt();
				// 补上数的前几位是0的0,不足四位的前几位补0
				int zero = 4 - String.valueOf(fib[x]).length();
				while (zero-- > 0) {
					System.out.print("0");
				}
				System.out.print(fib[x]);
			}
		}
	}
}