H题

前置知识

• gcd(m,n)=n?gcd(n,m%n):m;
• 

首先，这题真的简单

gcd与lcm，这边提供两种思路及3种AC代码。

首先，我们看题目不难发现，一共给了2种数据

分别是日期的gcd值和lcm值。

解法1

首先我们不难想到，全部搜一遍，查看是否存在多个日期的gcd和lcm与目标相同。

于是下面的代码

#include<bits/stdc++.h>
#include<cmath>
using namespace std;

const int N =1e6+10;
typedef pair<int,int> PII;
typedef long long ll;

bool pd(int a,int b){
    if(a==1||a==3||a==5||a==7||a==8||a==10||a==12){
        if(b<=0||b>31)return false;
    }
    else if(a==2){
        if(b<=0||b>29)return false;
    }
    else{
        if(b<=0||b>30)return false;
    }
    return true;
}

void solve(){
    int n,m;
    cin>>n>>m;
    vector<PII>vt;
    for(int i=1;i<=12;i++){
        for(int j=1;j<=31;j++){
            if(lcm(i,j)==n&&gcd(i,j)==m){
                vt.push_back({i,j});
            }
        }
    }
    for(int i = vt.size()-1;i>=0;i--){
        int a =  vt[i].first,b=vt[i].second;
        if(pd(a,b)==false){
            vt.erase(vt.begin() + i);
        }
    }

    if(vt.size()==1){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tt = 1;
    cin>>tt;
    while(tt--){
        solve();
    }
    return 0;
}

那么这种方法太慢了，平均每组样例的解决时间复杂度是，也就是大约要12*30次判断才能做出一组数据。

解法2，稍稍优化一下思路

上面的判断实在是太复杂了，每一个都去判断。

但是，有没有一种可能，

其实月份和日期随便选一个去判断，另一个其实同时也判断出来了。

由于已知 ，同时，令t为月份日期的积，我们用i去遍历月份，t/i其实就是日期。

接下来只需要判断 i 和 t/i 的gcd和lcm是否符合题目给出的，如果符合就用cnt计数。

遍历完12个月之后，判断 ,符合这个条件说明是唯一的，否则就是存在其他日期符合条件。

上AC 代码↓

#include <bits/stdc++.h>
#define int long long
using namespace std;

void zxy()
{
    int n,m;cin>>n>>m;
    int num = n * m;
    int month[12] = {31,29,31,30,31,30,31,31,30,31,30,31};
    int cnt = 0;
    for(int i=1;i<=12;i++)
    {
        if(num%i==0&&num/i<=month[i-1]&&gcd(i,num/i)==m&&lcm(i,num/i)==n) cnt ++;
    }
    if(cnt == 1) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

signed main()
{
    int t; cin>>t;
    while(t --) zxy();
    return 0;
}

解法3（暴力打表）

这个是出题时候写的解法，应该是本题目在数据量较大的情况下比较好的解法。

我们先建立一个二维数组，横纵坐标分别是gcd和lcm，一个1000，一个40足够了。

接下来预处理数据，遍历每个日期，计算gcd和lcm，并在对应的下标++，用于统计。

接下来只需要读入gcd和lcm，然后去数组里面查询是否唯一即可。

参考代码↓

#include "bits/stdc++.h"
using namespace std;
int main()
{
	int mp[373][32];
	memset(mp,0,sizeof mp);
	for(int i=1;i<13;i++)
	{
		for(int j=1;j<32;j++)
		{
			mp[lcm(i,j)][gcd(i,j)]++;
		}
	}
	int q;cin>>q;
	while(q--)
	{
		int l,g;cin>>l>>g;
		if(mp[l][g]==1)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}

记得补题