2020工大杯题解-B

发表于 更新于 分类于 本文字数： 527 阅读时长 ≈ 2 分钟

个人题解，和比赛官方无关，仅供参考

2020工大杯题解 - B - Classmate L’s PE course.

题目描述

Classmate L forgot to elect his course, so he had to take a strange PE course. On this strange course, students will play a weird game: each male student represent $a$, and each female students represent $b$. When a teacher says a non-zero positive integer number of $c$, $x$ male students and $y$ female students need to gather together and keep $ ax +
by = c $.

Classmate L is bad at math, he wants to know how many people he will be gathering together with.

Lots of students forgot to elect courses too, so we can assume that there is an infinite number of male and female students.

输入数据

One line containing three non-zero positive integer $n$, $a$, $b$. $\left(0 \leq n \leq 100, 2 \leq a,b \leq 10^4 \right)$.

Meaning of $a$ and $b$ are described above. $n$ means there will be $n$ queries.

For the next $n$ line, each line contains a non-zero positive integer $c$. $\left( 0 \leq c \leq 10^6 \right)$

输出数据

For each query, output the number of male students and the number of
female students separated by a space.

If it’s not possible form $c$, output ARE YOU KIDDING ME?.

If there are multiple answers, output the answer as the greatest
number of male students.

样例输入

1
2
3
2 2 3
1
100

样例输出

1
2
ARE YOU KIDDING ME?
49 0

题目大意

每个男生代表 $a$，每个女生代表$b$。每次询问一个数$c$，问你 L 同学需和要哪些人一起才能凑出来$c$。输出男生人数最大的方案。

相当于是求以下方程中 $x, y$ 的正整数解，同时要求$x \ge 1$， 输出$x-1, y$。

$$ax + by = c$$

思路

读入 $a, b, n$。 每次查询读入 $c$ , 起手直接 $c = c - a$ 。然后就是解方程。

进行时间复杂度分析：$0 \leq c \leq 10^6$， 直接暴力即可。

伪代码

1
2
3
4
5
6
7
读入a,b,n
循环 n 次：
	读入 c
	c = c - a
	枚举男生人数： 从（c/a） 到 0：
		算女生人数是否是整数， 是就输出
	如果失败， 输出ARE YOU KIDDING ME?

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
int main(){
    int n,a,b,c;
    cin>>n>>a>>b;
    while(n--){
        cin>>c;
        int x = 0;
        int y = 0;
        c -= a;
        for(x = c / a; x >= 0; x --){
            if ((c - a * x) % b == 0){
                y = (c - a * x) / b;
                break;
            }
        }
        if (x == -1) {
            cout<<"ARE YOU KIDDING ME?"<<endl;
        } else {
            cout<<x<<" "<<y<<endl;
        }
    }
    return 0;
}