我的青蛙终于过了
完全忘了算法导论上说的理论了~~其实以前写的就只有一个小错误
ax+ny=b;
当求解x时，我们先用扩展欧几里德extended_eculid(a,n,&x',&y');
通过计算的x'和y'来计算x
x可能没解，也可能有d个不同的解
当求解某些问题的时候，我们要求得到最小正解，如果x'*(b/d)<0时，我们应该在此解的基础上继续加n/d
青蛙问题我就是这里错了，我是在最小解的基础上加n,
最好不要忘了对n取模。
http://acm.pku.edu.cn/JudgeOnline/problem?id=1061
//SA-SB=kL(k为整数)
//SA=x+pm SB=y+pn
//(x-y)+p(m-n)=kL
//p(n-m)+kL=x-y
//ax+by=n<=>a'x+b'y=n/gcd(a,b)(此时a'与b'互质)
//若x0,y0为欧几里得所得解
//x=x0+b't y=y0-a't
#include<iostream>
__int64 Ext_Euclid(__int64 a,__int64 b,__int64* x,__int64* y)
{
__int64 p,q,d;
if(a==0){*x=0;*y=1;return b;}
if(b==0){*x=1;*y=0;return a;}
d=Ext_Euclid(b,a%b,&p,&q);
*x=q;
*y=p-(a/b)*q;
return d;
}
int main()
{
/*freopen("1.IN","r",stdin);
freopen("my.OUT","w",stdout);*/
__int64 x,y,m,n,l;//x为A的起始点,y为B的起始点
//m为x的步长，n为y的步长，l为纬度长
__int64 c,a,d;
__int64 p,q;
while(scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l)!=EOF){
if(n==m)printf("Impossible\n");
else {
if(m>n){a=m-n;c=y-x;}
else {a=n-m;c=x-y;}
d=Ext_Euclid(a,l,&p,&q);
if((x>y?(x-y):(y-x))%d)printf("Impossible\n");
else {
p*=c/d;
while(p<0)p+=l/d;//这里错了，最小的那个不是这么加的
p=p%l;
printf("%I64d\n",p);
}
}}
return 0;
}E
Encrypted
这道题就是简单的应用扩展的欧几里德，并不涉及模线性方程
#include<iostream>
#define MaxN 100005
char word[MaxN];
int data[MaxN],keys[MaxN];
typedef struct node{
int d;
int x;
int y;
void operator=(node b)
{
d=b.d;
x=b.x;
y=b.y;
}}NODE;
NODE EXTENDED_EUCLID(int a,int b)
{
NODE first,sec;
if(b==0){
sec.d=a;
sec.x=1;
sec.y=0;
return sec;
}
first=EXTENDED_EUCLID(b,(a%b+b)%b);
sec.d=first.d;
sec.x=first.y;
sec.y=first.x-(a/b)*first.y;
return sec;
}
int main()
{
int n,i;
node tmp;
while(scanf("%s",word)!=EOF){
memset(data,0,sizeof(data));
memset(keys,0,sizeof(keys));
int len=strlen(word);
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&data[i]);
for(i=0;i<n;i++)
scanf("%d",&keys[i]);
for(i=0;i<n;i++){
tmp=EXTENDED_EUCLID(data[i],keys[i]);
while(tmp.x<0)
tmp.x+=keys[i]/tmp.d;
printf("%c",word[tmp.x%len]);
}
printf("\n");
}
return 0;
}
posted on 2008-04-08 00:42
zoyi 阅读(180)
评论(0) 编辑 收藏 引用 所属分类:
acm 、
比赛总结