专注都难不倒 (4)

Ivan 说一片片的动态规划，这次是数学题了。

PART1: 纪念邮票

Problem

邮局最近推出了一套特殊的纪念邮票，这套邮票共有 N 张，邮票面值各不相同，按编号顺序为 1 分，2 分，．．．．．．，N 分。

小杭是个集邮爱好者，他很喜欢这套邮票，可惜现在他身上只有 M 分，并不够把全套都买下。他希望尽量买，最好刚好花光所有钱。作为一个集邮爱好者，小杭也不想买的邮票编号断断续续。所以小杭打算买面值 a 分至 b 分的 b-a+1 张连续的邮票，且总价值刚好为 M 分。

你的任务是求出所有符合要求的方案，以 [a,b] 的形式输出。

Input

输入文件只有一行，包含两个数 N 和 M（1<=N，M<=10⁹）。

Output

输出文件每行包含一个合法方案：[a,b]。按 a 值从小到大输出。

输出文件不含任何空格。

Sample Input

20 15

Sample Output

[1,5]
[4,6]
[7,8]
[15,15]

[important]
如果你简单使用求和公式 sum=(a+b)*(b-a+1)/2 的话必然就超时，数量级 10 的 9 次方，扫描完一遍天都亮了。
所以不如变换一下:
a+a+1+a+2+…+b=(1+2+3+..+h)+(a-1)*h
所以 M-(1+2+3+..+h) 可以被 h 整除，而使得 M 大于 1+2+3+..+h 的 h 又不会太多，所以就可以遍历 h 了。
[/important]

相关代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#define bits 100000
#include<iostream>
using namespace std;
 
int sum[bits];  //sum[i]记录1+2+3+...+i的值
int b[bits][2];  //b[i][2]记录结果
int pos=0;
int main()
{
	int N,M;
	scanf("{5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}d{5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}d",&N,&M);
	sum[0]=0;
	int i;
	for(i=1;i<bits;i++)
	{
		sum[i]=sum[i-1]+i;
		if(sum[i]>M)
			break;
	}         //初始化sum[i]=1+2+...+i
	pos=0;
	int len=1;
	while(1)
	{
		if(sum[len-1]>M)
			break;
		int remainder=(M-sum[len-1]){5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}len;
		if(remainder==0)
		{
			int begin=(M-sum[len-1])/len;
			int end=begin+len-1;
			if(end<=N&&begin>=1)
			{
				b[pos][0]=begin;
				b[pos][1]=end;
				pos++;
			}
		}
		len++;
	}
	for(i=pos-1;i>=0;i--)
	{
		printf("[{5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}d,{5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}d]n",b[i][0],b[i][1]);
	}
	return 0;
 
}

PART2:Rabbit

Problem

The rabbits have powerful reproduction ability. One pair of adult rabbits can give birth to one pair of kid rabbits every month. And after m months, the kid rabbits can become adult rabbits.

As we all know, when m=2, the sequence of the number of pairs of rabbits in each month is called Fibonacci sequence. But when m<>2, the problem seems not so simple. You job is to calculate after d months, how many pairs of the rabbits are there if there is exactly one pair of adult rabbits initially. You may assume that none of the rabbits dies in this period.

Input

The input may have multiple test cases. In each test case, there is one line having two integers m(1<=m<=10), d(1<=d<=100), m is the number of months after which kid rabbits can become adult rabbits, and d is the number of months after which you should calculate the number of pairs of rabbits. The input will be terminated by m=d=0.

Output

You must print the number of pairs of rabbits after d months, one integer per line.

Sample Input

2 3
3 5
1 100
0 0

Sample Output

5
9
1267650600228229401496703205376

[warning]
我做题的时候可没有最后一组测试数据的.. 而且一般这种题也不会给你这么大的提示说结果有这么长的
所以要高精度运算，这需要估计得出来大概要多少位才能容纳答案。
所以这道题还在于如何估计，我们可以估计出最多不会超过 2^100 次方，而 2^10 约等于 1000，那么用 35 位十进制就肯定可以装下了。
[/warning]

代码从略。