GDUT A.比比谁更大

发布于 2021-11-28  11 次阅读


题目概述

思路

  1. 暴力出不了奇迹(TLE)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long a,b;
void work()
{
    long long ans=1;
    for(int i=1;i<=a;++i)
    {
        ans*=i;
        if(ans>999068070)
            ans%=999068070;
    }
    a=ans,ans=1;
    for(int i=1;i<=b;++i)
    {
        ans*=i;
        if(ans>999068070)
            ans%=999068070;
    }
    b=ans;
}
int main()
{
    scanf("%lld%lld",&a,&b);
    work();
    if(a>b)
        printf("a is the winner!\n");
    else if(a<b)
        printf("b is the winner!\n");
    else printf("There is no winner!\n");
    return 0;
} 
  1. 巧取

    我们先观察一下取模运算的数999068070=103*19*17*13*11*7*5*3*2,我们惊讶的发现当到第103次阶乘时模结果等于0。

    所以a,b大于103时,结果一定为0。

#include<iostream>
using namespace std;
int main()
{
    int numa,numb;
    long long a=1,b=1;
    cin>>numa>>numb;
    for(int i=1;i<=numa;i++){
        a=(a*i)%999068070;
        if(a==0)break;
    }
    for(int i=1;i<=numb;i++){
        b=b*i%999068070;
        if(b==0)break;
    }
    if(a>b)printf("a is the winner!\n");
    else if(a<b)printf("b is the winner!\n");
    else printf("There is no winner!\n");
    return 0;
}