codeforce每日一题
题目链接
题目分数:1900
题目描述
输入 $T(≤100)$ 表示 $T$ 组数据。
每组数据输入 $x,d (2≤x,d≤1e9)$,保证 $x$ 是 $d$ 的倍数。
定义好数为 $d$ 的倍数。
定义美丽数为好数且不能表示为两个好数的乘积。
$x$ 能否表示为一个或多个美丽数的乘积,且表示方式不唯一?
输出 $YES$ 或 $NO$。
注:$2\*4$ 和 $4\*2$ 是同一种表示方式。
样例
输入样例1
8
6 2
12 2
36 2
8 2
1000 10
2376 6
128 4
16384 4
输出样例1
NO
NO
YES
NO
YES
YES
NO
YES
算法
(数论) $O(log(n))$
我们先找$x$中$d$因子的个数,并不断将$x$整除$d$,如果个数为$1$的话,直接输出$no$;否则判断$x$(注意,当前$x$和之后的$x$都是已经不包括$d$因子了)是否是质数,如果不是,那么可以将$x$分解,分别乘到不同的$d$中,结果不止一种,直接输出$yes$;如果$x$为质数则判断$d$是否为质数,若不为质数并且$d$因子的个数$>=3$,并且将$d$分解后与之前结构不同,也就是$x * x != d$,输出$yes$,其余情况都输出$no$。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd emplace_back
#define SZ(a) (int)a.size()
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 2e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
LL n, m;
inline void solve()
{
cin>>n>>m;
auto check = [&](LL x)
{
for(int i=2;i<=x/i;i++)
if(x % i == 0) return false;
return true;
};
int t = 0;
while(n % m == 0) t++, n /= m;
if(t <= 1) cout<<"NO"<<endl;
else{
if(!check(n)) cout<<"YES"<<endl;
else{
if(!check(m) && t > 2){
if(t > 3) cout<<"YES"<<endl;
else{
if(n * n == m) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
}
else cout<<"NO"<<endl;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}