首页 > 代码库 > hdu2769：枚举+同余方程
hdu2769：枚举+同余方程
题意：有一个随机数生成器 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：枚举+同余方程
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。