http://acm.hust.edu.cn/vjudge/contest/view.action?cid=26275#problem/B
Crawling in process...Crawling failedTime Limit:2000MS Memory Limit:65536KB 64bit IO Format:%lld & %llu
Description
The boy and Karlsson are dividing a chocolate that the boy's parents have presented him for his birthday. A chocolate is a rectangle that consists ofm × n chocolate squares, separated from each other by cutlines.
Of course, Karlsson does the dividing. First Karlsson divides the chocolate into two rectangular pieces, breaking it along some cutline. Since Karlsson wants to divide chocolate fairly, he would not be satisfied if the two pieces have different sizes. In this case he cuts away the piece equal to the smaller piece out of the larger piece, and eats it. If the pieces are still not equal, he does so again, and so on. After the pieces are finally equal, Karlsson eats one of the pieces, and the boy eats another.
Karlsson wants to make an initial cut in such a way that he would eat as much chocolate as possible. However, the boy knows that Karlsson likes chocolate very much, and he watches for the process closely. Karlsson must be very careful not to offend the boy. So he must not successively cut away and eat chocolate from the same piece --- this would seem too suspicious to the boy.
Help Karlsson to find out how much chocolate he can eat.
Input
There are mutiple cases in the input file.
Each case contains m and n (1 <= m, n <= 109 ).
There is an empty line after each case.
Output
Output one integer number --- how many chocolate squares Karlsson can eat. If Karlsson cannot divide chocolate using his method, output0 instead.
There should be am empty line after each case.Sample Input
6 5
Sample Output
24In the example Karlsson must initially break a chocolate into pieces of sizes 3 × 6 and 2 × 6 . After that he can eat all chocolate but the boy's piece that would finally be1 × 6 . Karlsson cannot, for example, cut a chocolate initially into pieces of sizes5 × 5 and 1 × 5 --- after doing so, he would have to successively cut a piece away from the first one several times, that would offend the boy.
思路就是从斐波那契数列出发，推理的过程如图：
最后 a*b a*b
2*a*b a*b
3*a*b 2*a*b
5*a*b 3*a*b....依次类推，要使得a*b最小必须使所取的斐波那契数最大，long long 以内的斐波那契数总共有91个，因此可以使用91以内的斐波那契数来进行计算。
#include<iostream>
#include<stdio.h>
using namespace std;
long long fib[92];
int main()
{
fib[0]=1;fib[1]=1;
for(int i=2;i<92;i++)
{
fib[i]=fib[i-1]+fib[i-2];
cout<<fib[i]<<endl;
}
long long m,n;
while(cin>>m>>n)
{
long long maxf=0;
for(int i=59;i>=0;i--)
{
if(m%fib[i]==0||n%fib[i]==0)
{
maxf=fib[i];break;
}
}
cout<<n*m-n*m/maxf<<endl;
cout<<endl;
}
return 0;
}