我的青蛙終于過(guò)了
完全忘了算法導(dǎo)論上說(shuō)的理論了~~其實(shí)以前寫(xiě)的就只有一個(gè)小錯(cuò)誤
ax+ny=b;
當(dāng)求解x時(shí)，我們先用擴(kuò)展歐幾里德extended_eculid(a,n,&x',&y');
通過(guò)計(jì)算的x'和y'來(lái)計(jì)算x
x可能沒(méi)解，也可能有d個(gè)不同的解
當(dāng)求解某些問(wèn)題的時(shí)候，我們要求得到最小正解，如果x'*(b/d)<0時(shí)，我們應(yīng)該在此解的基礎(chǔ)上繼續(xù)加n/d
青蛙問(wèn)題我就是這里錯(cuò)了，我是在最小解的基礎(chǔ)上加n,
最好不要忘了對(duì)n取模。
http://acm.pku.edu.cn/JudgeOnline/problem?id=1061
//SA-SB=kL(k為整數(shù))
//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)(此時(shí)a'與b'互質(zhì))
//若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的起始點(diǎn),y為B的起始點(diǎn)
//m為x的步長(zhǎng)，n為y的步長(zhǎng)，l為緯度長(zhǎng)
__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;//這里錯(cuò)了，最小的那個(gè)不是這么加的
p=p%l;
printf("%I64d\n",p);
}
}}
return 0;
}E
Encrypted
這道題就是簡(jiǎn)單的應(yīng)用擴(kuò)展的歐幾里德，并不涉及模線性方程
#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 閱讀(207)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
acm 、
比賽總結(jié)