【编程比赛】《AB计算器》

Eastsun

这个问题有一些难度，简单起见，大家可以不考虑高精度数的问题，用long代替即可。

yan

#include "stdio.h"
long cale(long a,long b,long c)
{long i;
for(i=0;i>=0;i++)if((c-a*i)%b==0||(c+a*i)%b==0)return(i);
return(-1);
}
void main()
{long a,b,c,n;
for(;;)
{printf("Input three numbers:");
  if(scanf("%d%d%d",&a,&b,&c)==EOF)break;
  n=cale(a,b,c);
  if(n!=-1)printf("The limit time is:%d\n",n);
  else printf("The number is over flow!\n");
}
}

yan

不知道对不对.

Eastsun

怎么说呢，楼上的算法是对的，但不是有效的算法。

这里有这个题目的一些测试数据，可以看到，有输出结果高达808422984072，再考虑到高精度计算所需的时间，楼上的算法是很难在有效的时间内得到结果的。

yan

确实,淘汰算法很耗时间

loglave

贴段代码,不是完整的解法,不过感觉就是使用下面的方法了,应该不超时的

/***********************************************
功能：
求ax+by=d,d为a,b 的最小公约数
入参：
出参：
a,b的最小公约数
保证x>0
***********************************************/
long gcd(long a,long b,long &x,long &y)
{
long k[2][2],f=1,t;
long a1,b1;
a1=a;
b1=b;
k[0][0]=k[1][1]=1;
k[0][1]=k[1][0]=0;
while(b!=0)
{
  k[1-f][0]=k[1-f][0]-a/b*k[f][0];
  k[1-f][1]=k[1-f][1]-a/b*k[f][1];
  t=a%b;
  a=b;
  b=t;
  f=1-f;
}
x=k[1-f][0];
y=k[1-f][1];
//保证x>0
if(b1>0)
{
  while(x<=0)
  {
   x+=b1;
   y-=a1;
  }
}
else
{
  while(x<=0)
  {
   x-=b1;
   y+=a1;
  }
}
return a;
}

/***********************************************
功能：
求a*x (mod n)= b(mod n) 的所有解
入参：
出参：
返回最小解
***********************************************/
long modular(long a,long b,long n)
{
long x,y,d,e,i;
d=gcd(a,n,x,y);
if(b%d!=0) return -1;
else
{
  e=x*(b/d)%n;
  return e;
}
/*计算所有解的方法*/
/*int answer[n];
for(i=0;i<n-1;i++)
{
  answer=(e+i*n/d)%n;
}*/
}

cheelumbill

我支持楼上，作为欧几里德算法的补充应该比较有效。

[此贴子已经被作者于2006-5-14 19:55:39编辑过]

Eastsun

Euler算法？是Euclid算法吧。

Eastsun

AB计算器

  程序文件名: ab.cpp/ab.pas/...  

　　南开ACM协会的一位元老设计了一种特殊的计算器。这个计算器只有四个键(A,B,+,-)。
　　计算器显示的数值开始为c，
　　按一下"+"然后按一下"A"，计算器显示的数值增加 a
　　按一下"-"然后按一下"A"，计算器显示的数值减少 a
　　按一下"+"然后按一下"B"，计算器显示的数值增加 b
　　按一下"-"然后按一下"B"，计算器显示的数值减少 b
　　请问至少需要按多少下A键才能让计算器显示的值显示为0
　　


  输入 （请使用标准输入输出，而不要读写文件）

　　输入包含三个正整数 a 、 b 、 c ，以空格隔开，满足 0<a<2^95 ， 0<b<2^95 ， 0<c<2^95 ， a 、b 分别表示A键和B键的对应数值， c 表示计算器显示的初始值。(2^95 表示2的95次幂)


输出 （请使用标准输入输出，而不要读写文件）

　　输出只有一个数，即为 A 键被按的次数的最小值(我们确保输入的情况都有对应的答案)


样例输入1样例输出17 12 8 4样例输入2样例输出210549830 6549835 5      140969

参考代码

3. //JAVA，支持高精度。
5. import java.math.BigInteger;
6. import java.io.*;
7. import java.util.*;
8. public class Ab{
9. private static BigInteger[] solve(BigInteger a,BigInteger b,BigInteger c){
10.   //解方程:ax+by=c,其中b>a>0
11.   BigInteger g = a.gcd(b);
12.   //if(!c.mod(g).equals(BigInteger.ZERO)) return null;
13.   //本题该方程一定有解，否则加上上一行注释掉的代码即可。
14.   a =a.divide(g);
15.   b =b.divide(g);
16.   c =c.divide(g);
17.   BigInteger[] s =new BigInteger[2];
18.   if(a.equals(BigInteger.ONE)){
19.   s[0] = c.subtract(b);
20.   s[1] = BigInteger.ONE;
21.   }
22.   else{
23.   BigInteger c1 =c.divide(a),c2 =c.remainder(a);
24.   BigInteger b1 =b.divide(a),b2 =b.remainder(a);
25.   BigInteger[] t =solve(b2,a,c2);
26.   s[1] =t[0];
27.   s[0] =c1.subtract(b1.multiply(s[1])).add(t[1]);
28.   }
29.   return s;
30. }
31. public static BigInteger result(BigInteger a,BigInteger b,BigInteger c){
32.   BigInteger[] s;
33.   if(a.compareTo(b)>0){
34.   BigInteger[] t=solve(b,a,c);
35.   s =new BigInteger[2];
36.   s[0] =t[1];
37.   s[1] =t[0];
38.   }
39.   else{
40.   s =solve(a,b,c);
41.   }
42.   BigInteger g =a.gcd(b);
43.   BigInteger d =b.divide(g);
44.   BigInteger m =s[0].mod(d),n =d.subtract(m);
45.   return m.compareTo(n)<0?m:n;
46. }
47. public static void main(String[] args){
48.   Scanner scan =new Scanner(System.in);
49.   BigInteger a =scan.nextBigInteger(),b =scan.nextBigInteger(),c =scan.nextBigInteger();
50.   System.out.print(result(a,b,c));
51. }
52. }
53.   

复制代码

[此贴子已经被作者于2006-5-11 2:31:55编辑过]