Day 0x8 UVa10193 All You Need Is Love

• Virtual Judge
• ZeroJudge

题意

• 输入两字串 S1、S2，问是否能找出对两字串皆合法的 L？
• 需要注意的点有：
  1. 会先输入一正整数 N 代表测资数
  2. 每两行输入为一笔测资
  3. 每笔测资的 S1、S2 皆为二进位字串
  4. 每行输入不超过 30 个字元
  5. 所有输入皆为合法字串
     • 开头不为 0
     • 至少两位元
  6. 什麽是合法的 L？
     • 重复 S - L (二进位减法) 直到 S = L
  7. 输出格式
     • p 代表第几笔测资
     • Pair #p: All you need is love!
     • Pair #p: Love is not all you need!

解法

• 思路
  • 一直重复用 S - L，其实就是看 S 是不是 L 的倍数，题目有举例：

  S = 11011 = 27
  L =    11 =  3
  
    bin   dec
  11011 =  27
  11000 =  24
  10101 =  21
  10010 =  18
   1111 =  15
   1100 =  12
   1001 =   9
    110 =   6
     11 =   3
  

  • 所以要检查有没有一数字同时对两字串 S1、S2 都合法，代表 L 要同时为两者的公因数，所以用 GCD 检查两者是否互质 (GCD = 1)；先把输入转成十进位比较好处理
• 老套路，输入测资数 N 後，用 while 回圈重复读入两字串存到字元阵列里

  int N;
  
  scanf("%d", &N);
  
  while(N--){
  
      char S1[31] = {0};
      char S2[31] = {0};
  
      scanf("%s%s", S1, S2);
  
      ...
  }
  

• 把字串代表的二进位转成十进位

  int str_to_int(char *a, char *b){
  
      int num1 = 0, num2 = 0;
      int i;
  
      for(i = 0; i < strlen(a); i++){
          num1 = (num1 << 1) + (a[i] - '0');
      }
  
      for(i = 0; i < strlen(b); i++){
          num2 = (num2 << 1) + (b[i] - '0');
      }
  
      return GCD(num1, num2);
  }
  

• 跟上篇 Day 0x7 UVa11417 GCD 一样用个邪教递回

  int GCD(int a, int b){
      return b == 0 ? a : GCD(b, a % b);
  }
  

• 判断回传是不是互质，再照规则输出即可

  if(str_to_int(S1, S2) != 1){
      printf("Pair #%d: All you need is love!\n", Case++);
  }
  else{
      printf("Pair #%d: Love is not all you need!\n", Case++);
  }
  

• C code

  #include<stdio.h>
  #include<string.h>
  
  int GCD(int a, int b){
      return b == 0 ? a : GCD(b, a % b);
  }
  
  int str_to_int(char *a, char *b){
  
      int num1 = 0, num2 = 0;
      int i;
  
      for(i = 0; i < strlen(a); i++){
          num1 = (num1 << 1) + (a[i] - '0');
      }
  
      for(i = 0; i < strlen(b); i++){
          num2 = (num2 << 1) + (b[i] - '0');
      }
  
      return GCD(num1, num2);
  }
  
  int main(){
  
      int N, Case = 1;
  
      scanf("%d", &N);
  
      while(N--){
  
          char S1[31] = {0};
          char S2[31] = {0};
  
          scanf("%s%s", S1, S2);
  
          if(str_to_int(S1, S2) != 1){
              printf("Pair #%d: All you need is love!\n", Case++);
          }
          else{
              printf("Pair #%d: Love is not all you need!\n", Case++);
          }
      }
  
      return 0;
  }
  

• C++
  • 十进位转二进位可以用 stoi()
    • std::stoi
  • 其他也有像 dec、hex、oct 可用
    • std::dec, std::hex, std::oct
  • 最大公因数可用 gcd()，但 C++17 才支援
    • std::gcd
      
• C++ code

  #include <bits/stdc++.h>
  using namespace std;
  
  int GCD(int a, int b){
      return b == 0 ? a : GCD(b, a % b);
  }
  
  int main(){
  
      int N, Case = 1;
  
      cin >> N;
  
      while(N--){
  
          string S1, S2;
  
          cin >> S1 >> S2;
  
          int num1 = stoi(S1, nullptr, 2), num2 = stoi(S2, nullptr, 2);
  
          if(GCD(num1, num2) != 1){
              cout << "Pair #" << Case++ << ": All you need is love!\n";
          }
          else{
              cout << "Pair #" << Case++ << ": Love is not all you need!\n";
          }
      }
  
      return 0;
  }