当前位置: 代码迷 >> 综合 >> HDOJ2104 hide handkerchief
  详细解决方案

HDOJ2104 hide handkerchief

热度:74   发布时间:2023-12-14 01:50:27.0

题目链接:hide handkerchief

题目的意思就是,有N个人围在一圈玩找手帕的游戏,每个人背后都有一个盒子,但只有一个盒子有手帕。

现在叫HaHa来找,他的找法是:定义一个M,每隔M-1个人找一次。

问HaHa是否一定能找到手帕。

他这样找手帕会出现一个问题,就是,有些人可能永远不会被找,出现死循环。

也就是如果N和M不互质的话就会出现有些人永远不会被找的情况。

现在将问题转化为了互质,互质的话,就是求他两的最大公约数,是1,就OK

下面AC代码:

import java.util.Scanner;public class Main{private static Scanner scanner;public static void main(String[] args) {scanner = new Scanner(System.in);while(scanner.hasNext()){int n = scanner.nextInt();int m = scanner.nextInt();if(n == -1 && m == -1){break;}int t;while(m != 0){//求公约数t = n%m;n = m;m = t;}if(n == 1){//如果最大公约数是1,就可以找到System.out.println("YES");}else {System.out.println("POOR Haha");}}}
}


  相关解决方案