[洛谷 P2312]解方程

danihao123 posted @ 2016年8月21日 21:32 in 题解 with tags NOIP 数学 数论 洛谷 , 172 阅读
转载请注明出处:http://danihao123.is-programmer.com/

最凶残的NOIP题。

首先我们可能会想到暴力枚举验证(枚举[tex][1,m][/tex]带入),然后我们很快就会想到用几个素数取模乱搞。然后嘛……

对于我们用到的取模数[tex]k[/tex],带入任意[tex]x[/tex],都有[tex]x^{a}\ mod\ k \in Z_{k} (a \in N^{0})[/tex](废话),所以说实际上我们枚举带入的是[tex][1,k)[/tex]。

这个题可以不开高精,因为可以一边读入一边取模

代码:

#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn=105,maxm=1000005;
const int P1=3079,P2=3083,P3=1000000207;

int X1[maxn],X2[maxn],X3[maxn];
bool Ac_1[P1],Ac_2[P2];

typedef long long ll;

inline ll mul_mod(ll a,ll b,ll Mod){
    return ((a%Mod)*(b%Mod))%Mod;
}

inline int readint(){
    register int ans=0;
    register char c=getchar();
    while(!isdigit(c)){
        c=getchar();
    }
    while(isdigit(c)){
        ans=ans*10+c-'0';
        c=getchar();
    }
    return ans;
}
inline void read_mod(int& a,int& b,int& c){
    a=b=c=0;
    bool flag=false;
    register char cr=getchar();
    while(!isdigit(cr)){
        if(cr=='-')
            flag=true;
        cr=getchar();
    }
    while(isdigit(cr)){
        a=(mul_mod(10,a,P1)+cr-'0')%P1;
        b=(mul_mod(10,b,P2)+cr-'0')%P2;
        c=(mul_mod(10,c,P3)+cr-'0')%P3;
        cr=getchar();
    }
    if(flag){
        a=(P1-a)%P1;
        b=(P2-b)%P2;
        c=(P3-c)%P3;
    }
}

int n;
bool check(int* A,int x,int Mod){
    int now=0;
    register int i;
    for(i=n;i>=0;i--){
        now=(mul_mod(now,x,Mod)+A[i])%Mod;
    }
    return now==0;
}

vector<int> AnsList;
int main(){
    int m;
    register int i,ans_count=0;
    n=readint();
    m=readint();
    for(i=0;i<=n;i++)
        read_mod(X1[i],X2[i],X3[i]);
    for(i=1;i<P1;i++)
        Ac_1[i]=check(X1,i,P1);
    for(i=1;i<P2;i++)
        Ac_2[i]=check(X2,i,P2);
    for(i=1;i<=m;i++){
        if(Ac_1[i%P1] && Ac_2[i%P2] && check(X3,i,P3)){
            ans_count++;
            AnsList.push_back(i);
        }
    }
    printf("%d\n",ans_count);
    for(i=0;i<AnsList.size();i++){
        printf("%d\n",AnsList[i]);
    }
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter