Jug Hard

灰太狼 2022-06-12 02:29 378阅读 0赞

Description  
You have two empty jugs and tap that may be used to fill a jug. When filling a jug from the tap, you can only fill it completely (i.e., you cannot partially fill it to a desired level, since there are no volume measurements on the jug).

You may empty either jug at any point.

You may transfer water between the jugs: if transferring water from a larger jug to a smaller jug, the smaller jug will be full and there will be water left behind in the larger jug.

Given the volumes of the two jugs, is it possible to have one jug with some specific volume of water?

Input

The first line contains T, the number of test cases (1 ≤ T 100 000). Each test case is composed of three integers: a b d where a and b (1 ≤ a, b ≤ 10 000 000) are the volumes of the two jugs, and d is the desired volume of water to be generated. You can assume that d ≤ max(a,b).  
Output

For each of the T test cases, output either Yes or No, depending on whether the specific volume of water can be placed in one of the two jugs.  
Sample Input

3  
8 1 5  
4 4 3  
5 3 4  
Sample Output

Yes  
No  
Yes

题意：给你两个空的罐子，问你是否可以用这两个罐子获得一定体积的水，这两个罐子上都没有确定的刻度，若要用罐子接水则必须要接满。

思路：若这两个罐子的体积最大公约数是要获得的水的体积的因子则可以；否则不行。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    int gcd(int a,int b)
    {
        return b==0?a:gcd(b,a%b);
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
           int a,b,c;
           scanf("%d %d %d",&a,&b,&c);
           if(c%gcd(a,b)==0)
            printf("Yes\n");
           else
            printf("No\n");
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，378人围观）

还没有评论，来说两句吧...

相关阅读

相关 PVE booting from Hard Disk

问题 exsi 虚拟机迁移到PVE，在pve创建一个相同规格的虚拟机随后使用下面命令，把exsi迁移过来的磁盘文件挂载，一切顺利，然后开机发现不到硬盘，如下图

蔚落/ 2023年01月23日 13:48/ 0 赞/ 274 阅读

相关 hard negative mining method

A standard solution, known as hard negative mining, is to iteratively grow, or bootstrap

叁歲伎倆/ 2022年12月17日 07:24/ 0 赞/ 79 阅读

相关 Linux中soft nproc 、soft nofile和hard nproc以及hard nofile配置

Linux中soft nproc 、soft nofile和hard nproc以及hard nofile配置 "soft" 和 "hard" 的区别 soft

ゞ浴缸里的玫瑰/ 2022年11月30日 12:57/ 0 赞/ 579 阅读

相关 LeetCode - Hard - 37. Sudoku Solver

Topic Backtracking Description [https://leetcode.com/problems/sudoku-solver/][

朱雀/ 2022年11月15日 11:18/ 0 赞/ 85 阅读

相关 135. Candy (Hard)

135. Candy (Hard) 题目描述一群孩子站成一排，每一个孩子有自己的评分。现在需要给这些孩子发糖果，规则是如果一个孩子的评分比自己身旁的一个孩子

深碍√TFBOYSˉ_/ 2022年11月03日 01:35/ 0 赞/ 115 阅读

相关 leetcode 365. Water and Jug Problem | 365. 水壶问题（Java）

题目 [https://leetcode.com/problems/water-and-jug-problem/][https_leetcode.com_problems

矫情吗；*/ 2022年08月30日 01:57/ 0 赞/ 95 阅读

相关 Jug Hard

Description You have two empty jugs and tap that may be used to fill a jug. When filli

灰太狼/ 2022年06月12日 02:29/ 0 赞/ 379 阅读

相关 hdu--6127--Hard challenge

Hard challenge Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 524288/524288

绝地灬酷狼/ 2022年06月10日 09:40/ 0 赞/ 86 阅读

相关 HDU-5858-Hard problem

Hard problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (J

缺乏、安全感/ 2022年05月27日 14:06/ 0 赞/ 107 阅读

相关 P、NP、NPC、NP-Hard问题

时间复杂度表明问题规模扩大后，程序需要的时间长度增长得有多快。程序的时间复杂度一般可以分为两种级别： \[1\] \- 多项式级的复杂度，如O(1)，O(log

我就是我/ 2022年05月25日 09:59/ 0 赞/ 182 阅读