卢卡斯数列

题目描述

卢卡斯数列规则如下：

（1）初始两个数字：A0 = 2，A1 = 1

（2）从 i ≥ 2 开始，每个新数字 Ai =  A(i-1) + A(i - 2)。

现在给定一个整数 n，请你计算 An 的值。

输入格式

一个整数 n。

输出格式

一个整数，表示第 n 项卢卡斯数。

输入样例1

4

输出样例1

7

输入样例 #2

86

输出样例 #2

939587134549734843

说明提示

0 ≤ n ≤ 86， 保证 An < 10^18。

国际象棋

题目描述

有一个 N x N 的巨大棋盘，包含 N^2 个格子。棋盘的行和列都从 1 到 N 编号，格子(i, j) 表示第 i 行第 j 列的格子。

目前棋盘上已经放置了 M 个马，第 k 只马位于格子 (ak, bk)。每个格子保证最多只能有一个棋子。

请统计，这个棋盘上有多少空格子，不会被任意一只马吃掉。

如果一只马在 (i, j)，那么它可以攻击以下 8 个位置（这些位置需要在棋盘边界范围内）：

（1）(i + 2, j + 1)

（2）(i + 1, j + 2)

（3）(i - 1, j + 2)

（4）(i - 2, j + 1)

（5）(i - 2, j - 1)

（6）(i - 1, j - 2)

（7）(i + 1, j - 2)

（8）(i + 2, j -1)

输入格式

第一行包含两个整数 N 和 M，分别表示棋盘大小和已有棋子数量。

接下来 M 行，每行包含两个整数 ak 和 bk，表示第 k 个棋子的位置。

输出格式

输出一个整数，表示可以安全放置棋子的空格子数量。

输入样例1

2 1
1 1

输出样例1

3

输入样例2

3 7
3 2
1 3
2 3
3 3
3 1
2 1
1 1

输出样例2

1

数据范围

1≤N≤10^9，1≤M≤2×10^5，1<=ak、bk<=N，所有棋子位置互不相同，输入均为整数。

魔法卷轴

题目描述

你是一名卷轴师，准备制作法卷轴。制作卷轴时，总成本为 a×n + b×d(n)，其中 n 是卷轴的数量，d(n) 是 n 的十进制位数。

你拥有 x 单位魔法材料。请问你最多能制作多少个卷轴？如果连一个卷轴都不能制作，输出 0。

输入格式

行三个整数 a、b、x。

输出格式

一个整数，表示答案。

输入样例1

18 395432867 10840610026

输出样例1

404539679

输入样例2

5 826766933 11100722310

输出样例2

731963982

输入样例3

1234 56789 314159265

输出样例3

254309

数据范围

1≤a、b≤10^9，1<=x<10^18。

符文的共鸣

题目描述

在魔法世界中，有 n 个符文，每个符文有一个能量值 ai。当两个符文共鸣时，会产生能量，但能量过高时会溢出，只保留剩余部分。

具体来说，符文 i 和符文 j 共鸣产生的能量为 (ai + aj) mod 100000000。

请计算所有不同的符文对（即所有 i < j 的配对）共鸣能量的总和。

输入格式

第一行输入一个整数 n。

第二行输入 n 个整数 a1, a2, ……, an。

输出格式

输出一个整数，表示所有符文对共鸣能量的总和。

输入样例1

2
1 1

输出样例1

2

输入样例2

2
99999999 99999999

输出样例2

99999998

数据范围

2≤N≤100000，1≤ai≤10^8。