pour.cc

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

/*
Jiangsu Olympiad in Informatics
Training Problem

Task:            Pour the Wine
Author:          The 2001 ACM Asia Programming Contest - Dhaka(adept by Wenyuan Dai)
Algorithm:       Mathematical Method
Complex:         O(logn)
Code:            Wenyuan Dai
Date:            3-26-2002
Time Limit:      1 seconds(Pentium IV 1.5G)
*/
#include <stdio.h>

long long a, b;

inline long long gcd(long long a, long long b) {
  for (long long temp; temp = a % b; a = b, b = temp);
  return b;
}

main() {
  FILE* fin = fopen("pour.in", "r");
  FILE* fout = fopen("pour.out", "w");

  fscanf(fin, "%Ld %Ld", &a, &b);

  long long c = gcd(a, b);
  fprintf(fout, "%Ld\n", c);

  a /= c, b /= c;
  long long a0 = 1, a1 = 0, b0 = 0, b1 = 1, ta = a, tb = b;
  for (long long temp; b != 1;) {
    temp = a / b;
    a0 += b0 * temp, a1 += b1 * temp;

    temp = a % b, a = b, b = temp;

    temp = a0, a0 = b0, b0 = temp;
    temp = a1, a1 = b1, b1 = temp;
    
    a0 %= tb, a1 %= ta, b0 %= tb, b1 %= ta;
  }
  
  if (b0 * ta - b1 * tb == -1)
    fprintf(fout, "%Ld %Ld\n", b0, b1);
  else {
    a0 += b0 * (a - 1), a1 += b1 * (a - 1);
    fprintf(fout, "%Ld %Ld\n", a0 % tb, a1 % ta);
  }

  fclose(fin);
  fclose(fout);
  
  return 0;
}