牛客 数论只会GCD

链接:https://ac.nowcoder.com/acm/contest/283/D
来源:牛客网

题目描述

小西买了一堆肥宅快乐水和肥宅快乐茶,准备和室友比谁更肥宅。
快乐水有A瓶,快乐茶B瓶。
小西和室友的规则是这样的:
1. 小西先手,轮流到每个人的回合,每个回合只能喝剩余数量较多的饮料
2. 满足规则1的同时,每次只能喝另一种饮料剩余数量的正整数倍
3. 满足1、2的同时,不能超额喝饮料,也就是说剩下2瓶的时候不能喝大于2瓶的数量。
4. 每个人在自己的回合如果能喝完剩下的其中一种饮料,那么就获得胜利。
例如A=10,B=2。
小西只能喝快乐水,且只能喝2/4/6/8/10瓶快乐水。小西可以喝10瓶快乐水直接获得胜利。

小西和室友都是肥宅,所以他们都会才采取为了胜利最优的行动。
现在请你判断小西是否能赢得胜利。

输入描述:

第一行输入一个整数T,表示有T组数据
接下来T行,每行为一组数据,每行有两个正整数表示A和B的初始数量
 

输出描述:

对于每组数据,若小西可以获得胜利则输出一行“wula”,否则输出一行“mmp”,不需要输出引号
示例1

输入

复制
2
20 18
10 4

输出

复制
mmp
wula
题意:
A,B两种饮料,两个人喝,一次只能喝一种,而且是多的那种,喝的瓶数是少的那种的倍数(他们撑不撑死就不管我们的事了)看谁赢(把两种喝成一种)
典型的数论题,因为他们比较聪明,所以当出现弹性空间时我们的运算就可以结束了,让他们这群聪明人自己去弹性去。
a>b:
如果a/b>1即可以控制为a=a%b+x*b 那个人肯定赢
#include<iostream>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long a,b;
        cin>>a>>b;
        if(a<b)
        {
            long long c=a;
            a=b;
            b=c;
        }
        int c=0;
        while(a%b!=0)
        {
            //如果a/b>1即可以控制为a=a%b+x*b 那个人肯定赢
            long long t=a/b;
            if(t>1)
            {
                break;
            }
            else
            {
                c++;
            }
            long long k=a%b;
            a=b;
            b=k;
        }
        if(c%2==0)
        {
            cout<<"wula"<<endl;
        }
        else{
            cout<<"mmp"<<endl;
        }
    }
}

  

原文地址:https://www.cnblogs.com/mozheaishang/p/10084994.html