ACboy needs your help
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5963 Accepted Submission(s):
3250
Problem Description
ACboy has N courses this term, and he plans to spend at
most M days on study.Of course,the profit he will gain from different course
depending on the days he spend on it.How to arrange the M days for the N courses
to maximize the profit?
most M days on study.Of course,the profit he will gain from different course
depending on the days he spend on it.How to arrange the M days for the N courses
to maximize the profit?
Input
The input consists of multiple data sets. A data set
starts with a line containing two positive integers N and M, N is the number of
courses, M is the days ACboy has.
Next follow a matrix A[i][j],
(1<=i<=N<=100,1<=j<=M<=100).A[i][j] indicates if ACboy spend j
days on ith course he will get profit of value A[i][j].
N = 0 and M = 0 ends
the input.
starts with a line containing two positive integers N and M, N is the number of
courses, M is the days ACboy has.
Next follow a matrix A[i][j],
(1<=i<=N<=100,1<=j<=M<=100).A[i][j] indicates if ACboy spend j
days on ith course he will get profit of value A[i][j].
N = 0 and M = 0 ends
the input.
Output
For each data set, your program should output a line
which contains the number of the max profit ACboy will gain.
which contains the number of the max profit ACboy will gain.
Sample Input
2 2
1 2
1 3
2 2
2 1
2 1
2 3
3 2 1
3 2 1
0 0
1 2
1 3
2 2
2 1
2 1
2 3
3 2 1
3 2 1
0 0
Sample Output
3
4
6
4
6
Source
Recommend
对于两个最简的分数 a / b, c / d 把他们两个的最小公倍数 x / y 也设为一个分数形式，那么这个 x 一定能够被 a , c整除， y 一定能够整除 b , d。那么要求得最小公倍数，那么肯定是分子尽量小，即 a , c 的最小公倍数， 分母尽量大， 即 b , d 的最大公约数。
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
if (b==) return a;
else return gcd(b,a%b);
}
ll lcm(ll a,ll b)
{
return a/gcd(a,b)*b;
}
int main()
{
ll i,j,t,fz1,fz2,fm1,fm2,fz,fm,len1,len2,len3,len4,tmp;
char c;
cin>>t;
while (t--)
{
cin>>fz1>>c>>fm1;
cin>>fz2>>c>>fm2;
tmp=gcd(fz1,fm1);
fz1/=tmp;
fm1/=tmp;
tmp=gcd(fz2,fm2);
fz2/=tmp;
fm2/=tmp;
//cout<<tmp<<" "<<fz2<<" "<<fm2<<endl;
//fm=gcd(fm1,fm2); 题目给的分数不是最简！！！！
//fz=lcm(fz1,fz2);fz是俩分子的最小公倍数 后化简的话 fm已经变成两个数的最大公约数了 没法被用作化简了
//cout<<gcd(fz,fm)<<"aaaaaaaaa"<<endl;
//fz/=gcd(fz,fm);
//fm/=gcd(fz,fm);//用abcd fz1,fz2写成fz1,fm1了
if (gcd(fm1,fm2)==)
cout<<lcm(fz1,fz2)<<endl;
else
cout<<lcm(fz1,fz2)<<"/"<<gcd(fm1,fm2)<<endl;
} return ;
}
//很久之前做的很烦的一道题。