火题大战Vol.1 A.

• 2020 年 8 月 18 日
• 筆記
• 基础--高精度, 思维题

火题大战Vol.1 A.

题目描述

给定两个数\(x\),\(y\)，比较\(x^y\) 与\(y!\)的大小。

输入格式

第一行一个整数\(T\)表示数据组数。
接下来\(T\)行，每行两个整数\(x\),\(y\),表示\(T\)组数据。

输出格式

输出有\(T\)行，对于每一组数据，如果\(x^y \leq y!\)
输出 \(Yes\)，否则输出\(No\)。

样例

样例输入

3
1 4
2 4
3 4

样例输出

Yes
Yes
No

样例输入

5
50 100
37 100
200 1000
400 1000
20000 100000

样例输出

No
Yes
Yes
No
Yes

数据范围与提示

对于\(50\%\)的数据满足\(x \leq 8\),\(y \leq 10\)。
对于\(80\%\)的数据满足\(x\),\(y \leq 300\) 。
对于\(100\%\)的数据满足\(x\),\(y \leq 10^5\),\(T \leq 5\)。

分析

做法一：

比较套路，因为我们只需要比较数的大小，所以我们将\(a \times b\)转化为 \(log(a)+log(b)\)

代码

#include<bits/stdc++.h>
using namespace std;
typedef double db;
const double lqs=1e-9;
const int maxn=1e6+5;
db lg[maxn];
int main(){
	int t;
	scanf("%d",&t);
	for(int i=1;i<maxn;i++){
		lg[i]=log2(i);
	}
	while(t--){
		int xx,yy;
		scanf("%d%d",&xx,&yy);
		double ans1=0,ans2=0;
		for(int i=1;i<=yy;i++){
			ans1=ans1+lg[xx];
		}
		for(int i=1;i<=yy;i++){
			ans2=ans2+lg[i];
		}
		if(ans1-ans2>lqs) printf("No\n");
		else printf("Yes\n");
	}
	return 0;
}

做法二

压位高精，但是因为博主比较菜，所以只能得到\(80\)分

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
const int bas=1000;
struct bigint{
	int a[maxn],len;
	bigint(){
		memset(a,0,sizeof(a));
		len=0;
	}
	void qk(){
		for(int i=1;i<=len;i++) a[i]=0;
		len=0;
	}
	void Read(int aa){
		while(aa){
			a[++len]=aa%bas;
			aa/=bas;
		}
	}
	bigint operator *(const bigint &A)const{
		bigint C;
		C.len=A.len+len;
		for(int i=1;i<=A.len;i++){
			for(int j=1;j<=len;j++){
				C.a[i+j-1]+=A.a[i]*a[j];
			}
		}
		for(int i=1;i<=C.len;i++){
			if(C.a[i]>=bas){
				int cz=C.a[i]/bas;
				C.a[i+1]+=cz;
				C.a[i]%=bas;
			}
		}
		if(C.a[C.len+1]) C.len++;
		while(C.a[C.len]==0) C.len--;
		return C;
	}
	void Write(){
		for(int i=len;i>=1;i--){
			printf("%.4d",a[i]);
		}
		printf("\n");
	}
}ansa,ansb,zh;
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int xx,yy;
		scanf("%d%d",&xx,&yy);
		ansa.qk(),ansb.qk();
		ansa.Read(xx);
		zh.qk();
		zh.Read(xx);
		for(int i=1;i<yy;i++){
			ansa=ansa*zh;
		}
		ansb.Read(yy);
		for(int i=1;i<yy;i++){
			zh.qk();
			zh.Read(i);
			ansb=ansb*zh;
		}
		bool jud=0;
		if(ansa.len>ansb.len){
			printf("No\n");
			jud=1;
		}
		else if(ansa.len<ansb.len){
			printf("Yes\n");
			jud=1;
		}
		else {
			for(int i=ansa.len;i>=1;i--){
				if(ansa.a[i]>ansb.a[i]){
					printf("No\n");
					jud=1;
					break;
				}
				else if(ansa.a[i]<ansb.a[i]){
					printf("Yes\n");
					jud=1;
					break;
				}
			}
			if(jud==0)printf("Yes\n");
		}
	}
	return 0;
}