青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

Problem B : Always an Integer

Combinatorics is a branch of mathematics chiefly concerned with counting discrete objects. For instance, how many ways can you pick two people out of a crowd of n people? Into how many regions can you divide a circular disk by connecting n points on its boundary with one another? How many cubes are in a pyramid with square layers ranging from 1 × 1 to n × n cubes?


                   TFigure 1:T If we connect six points on the boundary of a circle, at most 31 regions are created.

Many questions like these have answers that can be reduced to simple polynomials in n. The answer to the first question above is n(n-1)/2, or (n^2-n)/2. The answer to the second is (n^4-6n^3+23n^2-18n+24)/24. The answer to the third is n(n+1)(2n+1)/6, or (2n^3+3n^2+n)/6. We write these polynomials in a standard form, as a polynomial with integer coefficients divided by a positive integer denominator. These polynomials are answers to questions that can have integer answers only. But since they have fractional coefficients, they look as if they could produce non-integer results! Of course, evaluating these particular polynomials on a positive integer always results in an integer. For other polynomials of similar form, this is not necessarily true. It can be hard to tell the two cases apart. So that, naturally, is your task.

Input
The input consists of multiple test cases, each on a separate line. Each test case is an expression in the form (P)/D, where P is a polynomial with integer coefficients and D is a positive integer denominator. P is a sum of terms of the form Cn^E, where the coefficient C and the exponent E satisfy the following conditions:
1. E is an integer satisfying 0 ≤ E ≤ 100. If E is 0, then Cn^E is expressed as C. If E is 1, then Cn^E is expressed as Cn, unless C is 1 or -1. In those instances, Cn^E is expressed as n or -n.
2. C is an integer. If C is 1 or -1 and E is not 0 or 1, then the Cn^E will appear as n^E or -n^E.
3. Only non-negative C values that are not part of the first term in the polynomial are preceded by +.
4. Exponents in consecutive terms are strictly decreasing.
5. C and D fit in a 32-bit signed integer.

 

See the sample input for details.
Input is terminated by a line containing a single period.

Output
For each test case, print the case number (starting with 1). Then print TAlways an integerT if the test casepolynomial evaluates to an integer for every positive integer n. Print TNot always an integerT otherwise. Print the output for separate test cases on separate lines. Your output should follow the same format as the sample output.

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

Output for the Sample Input
Case 1: Always an integer
Case 2: Always an integer
Case 3: Not always an integer

題目大概的意思是說:給定一個關于n的p次多項式,問該多項式是否為整值多項式。
根據定理:n次多項式f(n)是整值多項式當且僅當f(n)至少在n+1個連續的整數上都取整值。
只用將0-MAXPOW(取101)依次代入多項式的分子,并對分母d取模,判斷是否都為0即可。
至于為什么要取MAXPOW,而不是多項式f(n)的最大的次數max{pi}:為了使問題一般化,我們可以講所有的多項式都看成是MAXPOW次的,只不過當次數p>max{pi}時,其對應的系數ci全部為0,并不妨礙問題的解決。這樣一來,就不需要再額外求出f(n)的最大次數max{pi},使程序得到簡化。

399645  2009-04-23 07:44:07 Accepted 0.066 Minimum 19193  C++ 4119 - Always an integer
 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int MAXPOW = 101;
 5 int c[MAXPOW],d;
 6 char ch;
 7 
 8 int calculate(long long n){
 9     int i;
10     long long ans=0;
11     for(i=MAXPOW;i>=0;i--)
12         ans=(ans*n+c[i])%d;
13     return (int)ans;
14 }
15 bool judge(){
16     int i;
17     for(i=0;i<=MAXPOW;i++)
18         if(calculate(i)) return false;
19     return true;
20 }
21 int main(){
22     int end,ca=1,sign,value,pow;
23     while(true){
24         ch=getchar();
25         if(ch=='.'break;
26         memset(c,0,sizeof(c));
27         while(true){
28             end=0,scanf(")%n",&end);
29             if(end) break;
30             scanf("+");
31             sign=0,value=1,scanf("-%n",&sign);
32             scanf("%d",&value);
33             if(sign) value=-value;
34             scanf("%nn%n^%n",&pow,&pow,&pow);
35             if(pow>1) scanf("%d",&pow);
36             c[pow]+=value;
37         }
38         scanf("/%d",&d);
39         getchar();
40         printf("Case %d: ",ca++);
41         puts(judge() ? "Always an integer" : "Not always an integer");
42     }
43     return 0;
44 }

posted on 2009-04-23 12:51 極限定律 閱讀(1880) 評論(0)  編輯 收藏 引用 所屬分類: ACM-ICPC World Final 2008題解

<2009年4月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

導航

統計

常用鏈接

留言簿(10)

隨筆分類

隨筆檔案

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            狠狠狠色丁香婷婷综合激情| 国产精品视频免费观看| 永久免费视频成人| 欧美成人dvd在线视频| 乱码第一页成人| 99国产精品99久久久久久| 亚洲美女中出| 国产日产欧产精品推荐色| 久久影院午夜论| 欧美成人免费小视频| 亚洲一区二区欧美| 欧美亚洲一区二区在线观看| 亚洲第一久久影院| 一本色道久久88综合日韩精品| 国产精品永久入口久久久| 老鸭窝91久久精品色噜噜导演| 老鸭窝毛片一区二区三区 | 久久久综合免费视频| 91久久夜色精品国产网站| 99精品视频网| 在线看片一区| 一区二区91| 亚洲国产经典视频| 一区二区三区黄色| 亚洲国产成人porn| 亚洲综合精品自拍| 亚洲美女毛片| 久久男人av资源网站| 亚洲综合不卡| 欧美福利在线观看| 久久九九99| 国产精品毛片va一区二区三区| 欧美大片在线观看一区二区| 国产精品一区久久| 99国产精品久久久久久久久久 | 国产亚洲人成a一在线v站| 亚洲国产日韩欧美| 国产欧美日韩91| 日韩视频一区二区在线观看 | 亚洲网址在线| 欧美国产精品人人做人人爱| 久久久久久自在自线| 国产精品日韩二区| 亚洲最黄网站| 日韩视频一区二区三区在线播放| 久久精视频免费在线久久完整在线看| 中日韩在线视频| 欧美国产日韩在线| 欧美成人三级在线| 激情文学综合丁香| 欧美一区二区三区在线观看视频 | 香蕉国产精品偷在线观看不卡| 欧美国产三区| 亚洲精品免费一二三区| 亚洲国产女人aaa毛片在线| 久久精品国产一区二区三区免费看 | 亚洲国产高清在线| 久久久www| 久久人人97超碰精品888 | 免费看黄裸体一级大秀欧美| 久久综合一区| 在线播放亚洲| 狂野欧美一区| 亚洲成人在线网| 亚洲三级电影全部在线观看高清| 鲁大师成人一区二区三区| 欧美高清免费| 亚洲免费高清视频| 欧美三级欧美一级| 亚洲一区二区视频在线| 欧美在线一级视频| 精品不卡一区| 欧美~级网站不卡| 亚洲欧洲日产国产网站| 一区二区三区四区在线| 国产精品男gay被猛男狂揉视频| 中文在线资源观看网站视频免费不卡| 亚洲制服少妇| 国产亚洲一区在线播放| 久久一区二区三区国产精品| 欧美国产成人精品| 亚洲香蕉成视频在线观看| 国产精品午夜在线| 久久久久一区二区三区| 亚洲国产一区二区三区a毛片| 亚洲午夜小视频| 国产亚洲va综合人人澡精品| 久久资源在线| 日韩亚洲欧美一区二区三区| 久久国产精品久久久| 亚洲国产成人tv| 国产精品激情电影| 久久久精品动漫| 99视频超级精品| 久久色在线播放| 妖精成人www高清在线观看| 国产九色精品成人porny| 久久夜色精品| 亚洲欧美自拍偷拍| 亚洲二区免费| 久久aⅴ国产紧身牛仔裤| 日韩视频在线播放| 国产亚洲精品7777| 欧美日韩 国产精品| 久久久久国产精品一区二区| 99这里只有精品| 欧美成在线观看| 欧美在线欧美在线| 在线中文字幕一区| 亚洲国产精彩中文乱码av在线播放| 欧美体内she精视频在线观看| 老色批av在线精品| 欧美一区二区三区免费观看视频| 亚洲精品1区2区| 美女精品网站| 欧美一区二区三区在线免费观看| 日韩小视频在线观看| 伊人成人开心激情综合网| 国产精品日韩欧美一区二区| 欧美久久影院| 欧美a级在线| 久久综合亚州| 久久精品国产一区二区三| 亚洲欧美日韩国产一区二区| 一区二区三区视频在线看| 亚洲国产成人久久综合一区| 蜜桃伊人久久| 久久亚洲电影| 久久久蜜桃精品| 欧美专区亚洲专区| 欧美尤物巨大精品爽| 亚洲综合视频在线| 亚洲综合三区| 亚洲主播在线观看| 亚洲一区精品在线| 亚洲一区美女视频在线观看免费| 99精品久久久| 在线综合亚洲欧美在线视频| 99视频+国产日韩欧美| 亚洲美女av电影| 一本综合久久| 亚洲午夜日本在线观看| 亚洲欧美日韩综合国产aⅴ| 亚洲一区久久| 欧美在线一级va免费观看| 久久国产精品久久久| 久久亚洲高清| 欧美激情免费观看| 亚洲经典三级| 夜夜爽av福利精品导航 | 麻豆久久精品| 欧美高清视频一区| 亚洲欧洲在线视频| 99精品99久久久久久宅男| 正在播放欧美视频| 一本综合久久| 久久av一区二区三区漫画| 亚洲国产另类精品专区| 亚洲二区视频| 一区二区av在线| 亚洲欧美在线看| 久久免费视频网| 亚洲国产毛片完整版 | 亚洲大片在线| av不卡在线| 久久精品99无色码中文字幕| 久久久欧美精品sm网站| 欧美精品粉嫩高潮一区二区| 国产精品久久久久影院色老大 | 国产在线视频欧美一区二区三区| 国内激情久久| 一区二区日韩伦理片| 久久av资源网站| 亚洲福利精品| 亚洲综合第一| 欧美电影免费观看| 国产欧美日韩在线播放| 亚洲欧洲综合另类| 欧美一区二视频在线免费观看| 欧美大片在线观看| 亚洲欧美国产va在线影院| 女人天堂亚洲aⅴ在线观看| 国产精品高精视频免费| 亚洲高清自拍| 欧美在线观看视频| 亚洲精品视频在线观看免费| 欧美中文字幕久久| 国产精品电影在线观看| 91久久夜色精品国产九色| 欧美在线影院| 日韩午夜剧场| 老司机午夜精品视频在线观看| 国产精品欧美一区二区三区奶水 | 亚洲精品免费电影| 另类尿喷潮videofree| 亚洲男人的天堂在线| 欧美日韩在线电影| 亚洲精品免费一二三区| 欧美gay视频激情| 久久狠狠一本精品综合网|