题目概述
思路
- 暴力出不了奇迹(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;
}
- 巧取
我们先观察一下取模运算的数
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;
}
Comments | NOTHING