文档介绍：2011-5-28
NOI2011湖北省组队选拔赛第一试试题
第一题:数学作业(程序文件名:)100 分,运行时限:
1s
小 C 数学成绩优异,于是老师给小 C 留了一道非常难的数学作业题:
给定正整数 N 和 M,要求计算 Concatenate (1 .. N) Mod M 的值,其中 Concatenate (1 ..
N)是将所有正整数 1, 2, …, N 顺序连接起来得到的数。例如,N = 13, Concatenate (1 .. N)
= 12345678910111213.
小 C 想了大半天终于意识到这是一道不可能手算出来的题目,于是他只好向你求助,希望
你能编写一个程序帮他解决这个问题。
【输入格式】()
,输入文件只有一行且为用空格隔开的两个正整数N和M,其中
30%的数据满足1≤N≤1000000;100%的数据满足1≤N≤1018且1≤M≤109.
【输出格式】()
输出文件 仅包含一个非负整数,表示 Concatenate (1 .. N) Mod M 的值。
【输入输出样例1】
13 13 4
【输入输出样例2】
********** 1000000000 345678910
第二题:勾股定理(程序文件名:)100 分,运行时限:2s
沫沫最近在研究勾股定理。对于两个正整数 A 与 B,若存在正整数 C 使得 A2+B2=C2,且 A 与
B 互质,则称(A,B)为一个互质勾股数对。
有一天,沫沫得到了 N 根木棍,其长度都是正整数,她准备从中挑选出若干根木棍来玩拼
图游戏,为了使拼出的图案有凌乱美,她希望挑选出的木棍中任意两根的长度均不是互质勾股
数对。现在,沫沫想知道有多少种满足要求的挑选木棍的方案。由于答案可能很大,你只要输
出答案对 109+7 取模的结果。
【输入格式】()
,输入文件第一行是一个正整数N,表示共有多少根木棍。输
入文件第二行是用空格隔开的N个正整数h1, h2, …, hN,其中对1≤i≤N,hi表示第i根木棍的长
度。输入的数据保证30%的数据满足对1≤i≤N有1≤hi≤3000,另外30%的数据满足对1≤i≤N有
1≤hi≤200000,剩下的40%的数据满足对1≤i≤N有20000≤hi≤1000000,100%的数据满足
N≤1000000。
【输出格式】()
输出文件 仅包含一个非负整数,表示满足要求的挑选木棍的方案数对 109+7 取
模的结果。
【输入输出样例】
2011-5-28
4 8
5 12 35 5
样例解释:(5,12)与(12,35)是互质勾股数对,故满足要求的挑选木棍的方案有8种