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;
}