首页 > 代码库 > hdu2769：枚举+同余方程

hdu2769：枚举+同余方程

2024-07-26 04:06:25   213人阅读

 题意：有一个随机数生成器  x[i+1]=(a*x[i]+b)%10001

已知  x1,x3,x5...求 x2,x4,x6......

x的个数为 2n (n<=10000) a,b也在 0到10000之间

分析，有 a，b两个未知数，不好解方程，只能通过枚举

比赛的时候想了一下枚举a，b感觉复杂度略大 没敢写（后来据说姿势优美的暴力也能过）

正解是枚举 a，求b

带入x1，x3即可得到一个很简单的exgcd同余方程，对0，10000的每一个a，解出一个b进行验证即可

代码：

#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define mod 10001long long in[10010];long long out[10010];long long exgcd(long long a,long long b,long long &x,long long &y){    if(!b)    {        x=1;        y=0;        return a;    }    long long tt=exgcd(b,a%b,x,y);    long long t;    t=x;    x=y;    y=(t-a/b*y);    return tt;}int main(){    int n;    scanf("%d",&n);    for(int i=0;i<n;i++)        scanf("%I64d",in+i);    int ok=0;    for(long long i=0;i<=10000;i++)    {        long long c=((in[1]-i*i*in[0]%10001)%10001+10001)%10001;        long long a=i+1;        long long b=-10001;        long long x,y;        long long d=exgcd(a,b,x,y);        if(c%d)            continue;        long long t=abs(b/d);        x*=c/d;        x=(x%t+t)%t;        for(int j=0;j<n;j++)        {            out[j]=(i*in[j]+x)%10001;            if(j==n-1)            {                ok=1;                break;            }            if(((i*out[j]+x)%10001)!=in[j+1])                break;        }        if(ok)            break;    }    if(!ok)    {        puts("bug");    }    for(int i=0;i<n;i++)    {        printf("%I64d\n",out[i]);    }    return 0;}

 

hdu2769：枚举+同余方程


联系
我们