[数学][差分数列][数学归纳法][模拟] LA4119 Always an integer

题意:给出一个多项式,判断它是不是在所有整数点都取值为整数。

一个屌丝做法就是可以每次都随机数,只要数量足够一定可以把非整数判断出来。正解是利用数组差分的操作和取模的性质,自己想真的想不到。。

其实如果考虑思考方向的话,对于数据,一开始的思路应该是,既然有100个阶那肯定不是用某种解析的方式去做,而是选择一些点代入判定。这样的话问题变成了代入哪些点。首先如果分母上的数字比较小,那么可以算0-D之间的所有数字,但是D也很大,就没办法这么算了。这时候可以发现唯一可操作的只有阶的数量,然后就应该往这个方面去想了。。。当然这个数学归纳法的差分确实是有难度的,很难想到。。
沈阳赛得来的教训:模拟一定要在纸上写好所有情况再敲代码。。。

#include

using namespace std;
typedef long long LL;
const int maxn=1e6+5;
const int mod=998244353;

LL ps[105],op[105];
int mx;
int d;

LL pp(LL x,LL p)
{
    LL ans=1;
    while(p--)
        ans=ans*x%d;
    return ans;
}


bool check(int x)
{
    LL ans=0;
    for(int i=mx;i>=0;i--)
    {
        ans+=op[i]*ps[i]*pp(x,i)%d;//???
    }
    if(ans%d)
        return 0;
    else
        return 1;
}


int main()
{
    string str;
    int len,cs=0;
    while(cin>>str)
    {
        cs++;
        memset(op,0,sizeof(op));
        memset(ps,0,sizeof(ps));
        len=str.length();
        if(len==1)
            break;
        mx=0;
        int rp;
        for(int i=0; i
	

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据