[World Finals 2008]总是整数

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file Integer.in Output file Integer.out

【题目描述】

组合数学主要研究计数问题。比如,

-从n个人中选2个人的方法有多少种方法?

-圆周上有n个点,两两相连之后最后能把圆面分成多少部分?

-有一个金字塔,从塔顶开始每一层分别有,1×1,2×2,...n×n个小正方体,问一共有多少个小立体?

很多问题的答案都可以被写成多项式的形式。对应上面的问题,答案是:

-  n(n-1)/2

(n^4 - 6n^3 + 23n^2 - 18^n + 24)/24

n(n + 1)(2n + 1)/6, or (2n^3 + 3n^2 + n)/6

由于上述3个多项式都是计数问题的答案,因此当n取任意正整数时,这些多项式的值都是整数。当然,对于其他多项式,这个性质并不一定成立。

给一个形式如P/D(其中P是整系数多项式,D是正整数)的多项式,判断它是否在所有正整数处取的整数值。

【输入格式】

输入包含多组数据。每组数据仅一行,即一个多项式(P)/D,其中P是若干个形如Cn^E的项之和,其中系数C和E满足以下条件:

(1)E是一个满足0≤E≤100的整数。如果E=0,则Cn^E写成C;如果E=1,Cn^E写成Cn,除非C=1或者-1(c=1时写成n=-1是写成-n).

(2)C是一个整数。如果C为1或-1且E不是0或1,则Cn^E写成n^E-n^E.

(3)只有不在第一项的非负C的前面才会有一个加号。

(4)E的数值严格递减。

(5)C和D都在32位带符号整数范围内。

输入结束标志为单个句号(.)。

【输出格式】

对于每组数据,如果满足条件,输入"Always an integer",否则输出"Not always an integer"

【样例输入】

(n^2-n)/2 (2n^3+3n^2+n)/6 (-n^14-11n+1)/3 .

【样例输出】

Case 1: Always an integer Case 2: Always an integer Case 3: Not always an integer

【提示】

Difference Series

【来源】

Always an Integer,World Finals 2008,LA 4119

刘汝佳,《算法竞赛入门经典训练指南》表2.4