frankchenfu 的博客

frankchenfu 的博客

题解 UVA1069 【Always an integer】

posted on 2018-03-18 15:38:58 | under 题解 |

解法

这道题目的解决方法如下:对于每一个$n(1\le n \le 101)$,都把它带进去试一遍,如果每一个$n$都能够使多项式$P$被$D$整除,那么这个式子就总是一个整数。

那么为什么可以这么做呢?

我们不妨设这里多项式的次数最高项次数是$k$

(即$P(n)=a_1\cdot n^k+a_2\cdot n^{k-1}+...+ a_k\cdot n+a_{k+1}$)

那么:

  • 当$k=0$的时候,那么只有常数项,总是成立的。
  • 当$k=1$的时候,设多项式表示为$P(n)=xn+y$,则$$P(n+1)-P(n)=[x(n+1)+y]-(xn+y)=x.$$所以等差数列$P(1)+P(2)+...+P(n)$的公差就是$x$。由于需要验证每一个$n$均为$D$的倍数,等价于验证$P(1)$和$P(2)-P(1)$均为$D$的倍数。又因为如果其中一个条件$P(1)$是$D$的倍数得到验证,那么验证$P(2)-P(1)\equiv 0\pmod{D}$等价于验证$P(2)\equiv 0\pmod{D}$,所以只需验证$P(1),P(2)$
  • 当$k=2$的时候,设多项式表示为$P(n)=xn^2+yn+z$,则$$P(n+1)-P(n)=2an+a+b.$$类似的道理,我们需要验证$P(1),P(2)-P(1),P(3)-P(2)$,也等价于验证$$\begin{cases} P(1)\equiv 0\pmod{D} \\ P(2)\equiv 0\pmod{D} \\ P(3)\equiv 0\pmod{D} \end{cases}$$

以下$(k\le 100)$的数据同理可得。

所以,由于$k\le 100$我们只要验证每一个$n(1\le n \le 101)$是否都满足即可。

代码

作为一道直接输入多项式的题目,小伙伴们的字符串处理能力就需要好好锻炼一下了!(这道题目字符串确实调了我比较久的时间,细节比较多)这里我给几个提醒吧。

  • 如果系数$c_i=1$或$c_i=-1$,那么正负号后面没有数字,就需要特判了。
  • 输入数字的时候注意判断正负号。
  • 注意次数$e_i=0$和$e_i=1$的情况,后面没有^
  • 由于只需要验证是否是$D$的倍数,所以就可以边算边取模,避免溢出,否则验算时$n^k=(k+1)^k\approx 100^{100}$。 代码比较乱,大家凑合着吧:
#include<cstdio>
#include<cstring>
#include<cctype>
const int MAXN=100010;
typedef long long ll;
char opt[MAXN];
int d,c[MAXN];

ll qpow(ll x,int b){
    ll res=1;
    while(b){
        if(b&1)
            res=res*x%d;
        x=x*x%d;b>>=1;
    }
    return res;
}

int readint(char *s,char *t){
    int res=0;char *pos=s;
    do{
        res=(res<<3)+(res<<1)+*pos-'0';
        pos++;
    }while(pos<t);
    return res;
}

bool solve(char *s,char *t){
    bool fir=1;
    while(s<t){
        bool neg;int res=0,top=0;
        if(*s!='+'&&*s!='-')
            if(fir){
                fir=0;
                neg=0;
            }
            else{
                printf("\nError in pos %d,char %c\n",s-opt,*s);
                return 0;
            }
        else{
            neg=(*s=='-');
            s++;
        }
        if(!isdigit(*s))
            res=1;
        else while(s<t&&isdigit(*s)){
            res=(res<<3)+(res<<1)+*s-'0';
            s++;
        }
        if(*s=='n'){
            top=1;
            s++;
        }
        else
            top=0;
        if(*s=='^'){
            s++;top=0;
            while(s<t&&isdigit(*s)){
                top=(top<<3)+(top<<1)+*s-'0';
                s++;
            }
        }
        c[top]=neg?-res:res;
    }
    for(int i=0;i<=100;i++){
        ll tot=0;
        for(int j=0;j<=100;j++)
            if(c[j])
                tot=(tot+c[j]*qpow(i,j))%d; 
        if(tot%d)
            return 0;
    }
    return 1;
}

int main(){
    for(int CAS=1;~scanf("%s",opt+1);CAS++){
        int n=strlen(opt+1),pos=n;
        if(n==1&&opt[1]=='.')
            break;
        for(int i=n;i;i--,pos--)
            if(opt[i]=='/'&&opt[i-1]==')')
                break;
        memset(c,0,sizeof(c));
        d=readint(opt+pos+1,opt+n+1);
        if(solve(opt+2,opt+pos-1))
            printf("Case %d: Always an integer\n",CAS);
        else
            printf("Case %d: Not always an integer\n",CAS);
    }
    return 0;
}