OI题库

【题目描述】

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

-从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