andyli

题解 UVA1069 【Always an integer】
本题实际上是判断一个整系数多项式$P$的值是否总是正整数$D$的倍数。一个容易想到的方法是,随机代入很多整数计算$...
扫描右侧二维码阅读全文
20
2019/06

题解 UVA1069 【Always an integer】

本题实际上是判断一个整系数多项式$P$的值是否总是正整数$D$的倍数。一个容易想到的方法是,随机代入很多整数计算$P/D$,如果全都是整数,那么很有可能是Always an integer;如果有的不是整数,那么答案必然是Not always an integer
这个方法看起来有些投机取巧,但效果非常不错。事实上,不需要随机代入,只需要把$n=1,2,3,...,k+1$全试一遍就可以了,其中$k$试多项式中最高项的次数。
为什么可以这样做呢?让我们从$k$较小的情况开始研究。

  • 当$k=0$时,$P$里根本就没有$n$个变量,所以只需代入$P(1)$计算即可。
  • 当$k=1$时,$P$时$n$的一次多项式,设为$an+b$,则$P(n+1)-P(n)=a$。如果把$P(n)$看成一个数列的第$n$项,则$\{P(n)\}$是一个首项为$P(1)$,公差为整数$a$的等差数列,因此只要首项和公差均为$D$的倍数,整个数列的所有项都会是$D$的倍数。因此只需验证$P(1)$和$P(2)$。
  • 当$k=2$时,$P$是$n$的二次多项式,设为$an^2+bn+c$,则$P(n+1)-P(n)=2an+a+b$。注意到这个$2an+a+b$是$n$的一次多项式,根据刚才的结论,只要$n=1$和$n=2$时它都是$D$的倍数,对于所有的正整数$n$,它都将是$D$的倍数。这样,相邻两项的差为$D$的倍数,再加上首项也为$D$的倍数,则$P(n)$将总是$D$的倍数。整理一下,只要$P(1),P(2)-P(1),P(3)-P(2)$都是$D$的倍数即可。这等价于验证$P(1),P(2)$和$P(3)$。
    看到这里,结论已经不难猜到了。对于$k$次多项式$P(n)$,相邻两项之差$P(n+1)-P(n)$是关于$n$的$k-1$次多项式,根据数学归纳法,命题得证。顺别说一句,数列$dP(n)=P(n+1)-P(n)$称为$P(n)$的差分数列(difference series)。而差分数列的差分数列为二阶差分数列$d^2P(n)$,以此类推。

本题还要注意输入二项式的格式问题。输入格式翻译如下:
输入包含多组数据。每组数据仅一行,即一个多项式$(P)/D$,其中$P$是若干个形如$Cn^E$的项之和,其中系数$C$和$E$满足以下条件:

  1. $E$是一个满足$0\le E\le 100$的整数。如果$E=0$,则$Cn^E$写作$C$;如果$E=1$,则$Cn^E$写成$Cn$;除非$C$等于$1$或者$-1$($C=1$时写作$n$,$C=-1$时写作$-n$)。
  2. $C$是一个整数。如果$C$等于$1$或$-1$,且$E$不是$0$或者$1$,则$Cn^E$写成$n^E$或者$-n^E$。
  3. 只有不在第一项的非负$C$的前面才会有一个加号。
  4. $E$的数值严格递减。
  5. $C$和$D$都在$32$位带符号整数范围内。
    输入结束标志为单个英文句号(.)。

代码如下:

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
struct Polynomial
{
    vector<int> a, p;  // 第i项为a[i] * n^p[i]
    void parse_polynomial(string expr)
    {  // 解析多项式(不带括号)
        int i = 0, len = expr.size();
        while (i < len)
        {  // 每次循环体解析一个a*n^p
            int sign = 1;
            if (expr[i] == '+')
                i++;
            if (expr[i] == '-')
            {
                sign = -1;
                i++;
            }
            int v = 0;
            while (i < len && isdigit(expr[i]))
                v = v * 10 + expr[i++] - '0';  // 系数的绝对值
            if (i == len)
            {
                a.push_back(v);
                p.push_back(0);
            }  // 常数项
            else
            {
                if (v == 0)
                    v = 1;  // 无系数,按1处理
                v *= sign;
                if (expr[++i] == '^')
                {  // 有指数项
                    a.push_back(v);
                    v = 0;  // 清空v,接下来用v保存指数
                    i++;
                    while (i < len && isdigit(expr[i]))
                        v = v * 10 + expr[i++] - '0';
                    p.push_back(v);
                }
                else
                {  // 无指数项
                    a.push_back(v);
                    p.push_back(1);
                }
            }
        }
    }

    // 计算f(x)除以MOD的余数
    int mod(int x, int MOD)
    {
        int n = a.size(), ans = 0;
        for (int i = 0; i < n; i++)
        {
            int m = a[i];
            for (int j = 0; j < p[i]; j++)
                m = m * 1LL * x % MOD;    // 注意避免溢出
            ans = (ans * 1LL + m) % MOD;  // 加法也可能会溢出!
        }
        return ans;
    }
};

bool check(string expr)
{
    int p = expr.find('/');
    Polynomial poly;
    poly.parse_polynomial(expr.substr(1, p - 2));
    int D = stoi(expr.substr(p + 1));  // stoi是C++11新增的函数
    for (int i = 1; i <= poly.p[0] + 1; i++)
        if (poly.mod(i, D))
            return false;
    return true;
}

int main()
{
    int kase = 0;
    string expr;
    while (getline(cin, expr) && expr[0] != '.')
        printf("Case %d: %s\n", ++kase,
               check(expr) ? "Always an integer" : "Not always an integer");
    return 0;
}
Last modification:June 25th, 2019 at 11:22 am
If you think my article is useful to you, please feel free to appreciate

5 comments

  1. Karry5307

    什么回事,为什么他说我的评论不符合规则但又交上去了

    1. andyli
      @Karry5307

      某个插件导致的问题,已修复

  2. Karry5307

    现在还可以交UVa吗??我看大佬天天交UVa的题

    如果不能的话,那么大佬用什么交的?

  3. Karry5307

    现在还可以交UVa吗

    1. andyli
      @Karry5307

      可以交啊

Leave a Comment