质因数分解

【问题描述】

已知正整数 n 是两个不同的质数的乘积，试求出较大的那个质数。

【输入】

输入文件名为 prime.in。

输入只有一行，包含一个正整数 n。

【输出】

输出文件名为 prime.out。

输出只有一行，包含一个正整数 p，即较大的那个质数。

【输入输出样例】

【数据范围】

对于 60%的数据，6 ≤ n ≤ 1000。

对于 100%的数据，

寻宝

【问题描述】 传说很遥远的藏宝楼顶层藏着诱人的宝藏。小明历尽千辛万苦终于找到传说中的这个藏 宝楼，藏宝楼的门口竖着一个木板，上面写有几个大字：寻宝说明书。说明书的内容如下：

藏宝楼共有 N+1 层，最上面一层是顶层，顶层有一个房间里面藏着宝藏。除了顶层外，藏宝楼另有 N 层，每层 M 个房间，这 M 个房间围成一圈并按逆时针方向依次编号为 0，…，M-1。其中一些房间有通往上一层的楼梯，每层楼的楼梯设计可能不同。每个房间里有一个指示牌，指示牌上有一个数字 x，表示从这个房间开始按逆时针方向选择第 x 个有楼梯的房间（假定该房间的编号为 k），从该房间上楼，上楼后到达上一层的 k 号房间。比如当前房间的指示牌上写着 2，则按逆时针方向开始尝试，找到第 2 个有楼梯的房间，从该房间上楼。如果当前房间本身就有楼梯通向上层，该房间作为第一个有楼梯的房间。

寻宝说明书的最后用红色大号字体写着：“寻宝须知：帮助你找到每层上楼房间的指示牌上的数字（即每层第一个进入的房间内指示牌上的数字）总和为打开宝箱的密钥”。

请帮助小明算出这个打开宝箱的密钥。

【输入】

输入文件为 treasure.in。

第一行 2 个整数 N 和 M，之间用一个空格隔开。N 表示除了顶层外藏宝楼共 N 层楼，M 表示除顶层外每层楼有 M 个房间。

接下来 N*M 行，每行两个整数，之间用一个空格隔开，每行描述一个房间内的情况，其中第(i-1)*M+j 行表示第 i 层 j-1 号房间的情况（i=1, 2, …, N；j=1, 2, … ,M）。第一个整数表示该房间是否有楼梯通往上一层（0 表示没有，1 表示有），第二个整数表示指示牌上的数字。注意，从 j 号房间的楼梯爬到上一层到达的房间一定也是 j 号房间。

最后一行，一个整数，表示小明从藏宝楼底层的几号房间进入开始寻宝（注：房间编号从 0 开始）。

【输出】

输出文件名为 treasure.out。

输出只有一行，一个整数，表示打开宝箱的密钥，这个数可能会很大，请输出对 20123取模的结果即可。

【输入输出样例】

【输入输出样例说明】

第一层：

0 号房间，有楼梯通往上层，指示牌上的数字是 2；

1 号房间，无楼梯通往上层，指示牌上的数字是 3；

2 号房间，有楼梯通往上层，指示牌上的数字是 4；

第二层：

0 号房间，无楼梯通往上层，指示牌上的数字是 1；

1 号房间，有楼梯通往上层，指示牌上的数字是 5；

2 号房间，有楼梯通往上层，指示牌上的数字是 2；

小明首先进入第一层（底层）的 1 号房间，记下指示牌上的数字为 3，然后从这个房间开始，沿逆时针方向选择第3 个有楼梯的房间 2 号房间进入，上楼后到达第二层的2 号房间，记下指示牌上的数字为 2，由于当前房间本身有楼梯通向上层，该房间作为第一个有楼梯的房间。因此，此时沿逆时针方向选择第 2 个有楼梯的房间即为 1 号房间，进入后上楼梯到达顶层。这时把上述记下的指示牌上的数字加起来，即 3+2=5，所以打开宝箱的密钥就是 5。

【数据范围】

对于 50%数据，有 0<N≤1000，0<x≤10000；

对于 100%数据，有 0<N≤10000，0<M≤100，0<x≤1,000,000。

摆花

【问题描述】

小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 m 盆。通过调查顾客的喜好，小明列出了顾客最喜欢的 n 种花，从 1 到 n 标号。为了在门口展出更多种花，规定第 i 种花不能超过 ai盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。

试编程计算，一共有多少种不同的摆花方案。

【输入】

输入文件 flower.in，共 2 行。

第一行包含两个正整数 n 和 m，中间用一个空格隔开。

第二行有 n 个整数，每两个整数之间用一个空格隔开，依次表示 a1、a2、……an。

【输出】

输出文件名为 flower.out。

输出只有一行，一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 1000007 取模的结果。

【输入输出样例 1】

【输入输出样例说明】

有 2 种摆花的方案，分别是(1，1，1，2)， (1，1，2，2)。括号里的 1 和 2 表示两种花， 比如第一个方案是前三个位置摆第一种花，第四个位置摆第二种花。 

【数据范围】

对于 20%数据，有 0<n≤8，0<m≤8，0≤ai≤8；

对于 50%数据，有 0<n≤20，0<m≤20，0≤ai≤20；

对于 100%数据，有 0<n≤100，0<m≤100，0≤ ai≤100。

文化之旅

【问题描述】

有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。

现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使者游历的起点和终点（在起点和终点也会学习当地的文化），国家间的道路距离，试求从起点到终点最少需走多少路。

【输入】

输入文件 culture.in。

第一行为五个整数 N，K，M，S，T，每两个整数之间用一个空格隔开，依次代表国家个数（国家编号为 1 到 N），文化种数（文化编号为 1 到 K），道路的条数，以及起点和终点的编号（保证 S 不等于 T）；

第二行为 N 个整数，每两个整数之间用一个空格隔开，其中第 i 个数 Ci，表示国家 i的文化为 Ci。

接下来的 K 行，每行 K 个整数，每两个整数之间用一个空格隔开，记第 i 行的第 j 个数为 aij，aij= 1 表示文化 i 排斥外来文化 j（i 等于 j 时表示排斥相同文化的外来人），aij= 0 表示不排斥（注意 i 排斥 j 并不保证 j 一定也排斥 i）。

接下来的 M 行，每行三个整数 u，v，d，每两个整数之间用一个空格隔开，表示国家 u与国家 v 有一条距离为 d 的可双向通行的道路（保证 u 不等于 v，两个国家之间可能有多条道路）。

【输出】

输出文件名为 culture.out。

输出只有一行，一个整数，表示使者从起点国家到达终点国家最少需要走的距离数（如果无解则输出-1）。

【输入输出样例 1】

【输入输出样例说明】

由于到国家 2 必须要经过国家 1，而国家 2 的文明却排斥国家 1 的文明，所以不可能到达国家 2。

【输入输出样例 2】

【输入输出样例说明】

路线为 1 -> 2。

【数据范围】

对于 20%的数据，有 2≤N≤8，K≤5；

对于 30%的数据，有 2≤N≤10，K≤5；

对于 50%的数据，有 2≤N≤20，K≤8；

对于 70%的数据，有 2≤N≤100，K≤10；

对于 100%的数据，有