我的青蛙終于過了
完全忘了算法導論上說的理論了~~其實以前寫的就只有一個小錯誤
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 閱讀(196)
評論(0) 編輯 收藏 引用 所屬分類:
acm 、
比賽總結