首页 > ACM题库 > HDU-杭电 > HDU 1792 A New Change Problem-数论应用-[解题报告] C++
2013
12-23

HDU 1792 A New Change Problem-数论应用-[解题报告] C++

A New Change Problem

问题描述 :

Now given two kinds of coins A and B,which satisfy that GCD(A,B)=1.Here you can assume that there are enough coins for both kinds.Please calculate the maximal value that you cannot pay and the total number that you cannot pay.

输入:

The input will consist of a series of pairs of integers A and B, separated by a space, one pair of integers per line.

输出:

For each pair of input integers A and B you should output the the maximal value that you cannot pay and the total number that you cannot pay, and with one line of output for each line in input.

样例输入:

2 3
3 4

样例输出:

1 1
5 3

题目就是给了两个互质的数A,B。
A*x+B*y(x>=0,y>=0)
问最大不能表示的数,和不能表示的数的个数。
 
数论知识;
个数就是(A-1)*(B-1)/2;
最大不能表示的数就是 A*B-A-B;
#include<stdio.h>
 int main()
 {
     int A,B;
     while(scanf("%d%d",&A,&B)!=EOF)
     {
         printf("%d %d\n",A*B-A-B,(A-1)*(B-1)/2);
     }    
     return 0;
 }

解题报告转自:http://www.cnblogs.com/hxsyl/archive/2012/09/08/2677114.html


  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。