51nod 2143 锯木棍

题目

有一根粗细均匀长度为 LL 的木棍，先用红颜色刻度线将它 m 等分，再用蓝色刻度线将其 n 等分（m>n），然后按所有刻度线将该木棍锯成小段，计算并输出长度最长的木棍的长度和棍数。

例如：木棍长12，按照6,4划分。最长的木棍长度为2。共有4根。

输入
输入仅有一行，包含三个正整数 L，m 和 n，两两之间用一个空格分隔。（1≤L≤100000）
输出
输出包含两个正整数 a 和 k，分别表示最长木棍的长度和根数。(为了简化题目的难度，所有的测试数据中 m 和 n 一定是 L 的约数）。两数之间用一个空格分隔
输入样例
12 6 4
输出样例
2 4

解题思路

创建两个数组 一个表示锯的位置 一个表示木棍长度 先判断锯的位置 标记出来 带入第二个数组求出最长的木棍 有相同长度++

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <deque>
#include <list>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <iterator>
#define INT_MAX 0x7fffffff
#define INT_MIN 0x80000000
const int MOD = 1E9+7;
const int N = 100000+5;
using namespace std;

int stick[N];
int len[N];

int main()
{
    int L, m, n;

    cin >> L >> m >> n;

    int x = L/m;

    for(int i = 0; i*x<=L; i++){
        stick[i*x] = 1;
    }
    int y = L/n;

    for(int i = 0; i*y<=L; i++){
        stick[i*y] = 1;
    }
    int flag = 0;
    for(int i = 1; i <= L; i++){
        if(stick[i]==1){
            len[i-flag]++;
            flag = i;
        }
    }

    int a = 0;
    for(int i = 1; i <=L; i++){
        if(len[i]>0){
            a=i;
        }
    }
    cout << a << ' ' << len[a];
    return 0;
}