蓝桥云课 数的拆分（数论）

本文主要是介绍蓝桥云课 数的拆分（数论），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

觉得这个题挺好的，留个档，至于题解在题目上已经有讲的很好的了。

---

思路：

数学思维题。

对一个数 $x$，根据唯一分解定理可以拆成 $$x=p_1^{k_1}\ast p_2^{k_2}\ast p_3^{k_3}\ast \cdots \ast p_s^{k_s}$$的形式，然后我们要把这个形式转化为题目上 $x=q_1^{y_1}\ast q_2^{y_2}$ 的形式。

其实比较容易发现内部的 $q_1,q_2$ 还是可以再拆的，因此 $y_1,y_2$ 我们选择尽可能小的数会比较好凑。比如说 $q^6$ 和 $(q^3{)}^2$ 是完全相同的，但是后者的 $y=2$ 就比较好凑，指数为 $2$ 的倍数的情况显然更加常见。因此我们选择让 $y_1=2,y_2=3$。

这样，对一个质因数 $p_i^{k_i}$，我们需要 $q_1^{y_1}\ast q_2^{y_2}=q_1^2\ast q_2^3$ 包含它，假设 $q_1$ 有 $x$ 个 $p_i$，$q_2$ 有 $y$ 个 $p_i$，那么就有 $k_i=2\ast x+3\ast y$。而这个式子在 $k_i>1$ 时是总是有解的（非负整数解）。换句话说，只要 $k_i>1$，$p_i^{k_i}$ 就有办法分到 $q_1$ 和 $q_2$ 中去，否则就没可能。因此我们只要保证所有质因数都满足它的指数大于 $1$，那么就存在一种分配方案，把 $x$ 可以转化为 $q_1^{y_1}\ast q_2^{y_2}$ 的形式。

不过要分解质因数，我们需要筛到 $\sqrt{10^{18}}=10^9$ 以内的质因数，预处理就会超时。而且每个数我们都要分解一下，分解的时候需要枚举质因数，质因数的个数就不能太多。

考虑到当 $x$ 转化为 $q_1^{y_1}\ast q_2^{y_2}=q_1^2\ast q_2^3$ 的形式时，当 $q_1=1$ 或 $q_2=1$ 时，这个数就是个纯粹的平方数或者立方数，直接特判就行了。

当 $q_1,q_2\ne 1$ 时，这个数 $x$ 就至少拥有了 $5$ 个质因数。此时除了最大的质因数，其他较小的质因数一定都满足 $\le \sqrt[5]{10^{18}}\approx 3981$，剩下的那个较大的质因数 $q$ 只有可能是 $q^1,q^2,q^3,q^4$（再多 它的大小就小于 $\sqrt[5]{10^{18}}$ 了），除开指数是 $1$ 的情况，其他情况就是个平方数或者立方数，可以直接特判。

code：

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;ll prime[maxn],cnt;
bool vis[maxn];
void Eular(int n){vis[1]=true;for(int i=2;i<=n;i++){if(!vis[i])prime[++cnt]=i;for(int j=1,p=prime[1];j<=cnt && i*p<=n;p=prime[++j]){vis[i*p]=true;if(i%p==0)break;}}
}ll T,a;bool is2(ll x){ll l=1,r=x,mid;while(l<r){mid=l+r>>1;if(mid<=1e9 && mid*mid<x)l=mid+1;else r=mid;}return l*l==x;
}
bool is3(ll x){ll l=1,r=x,mid;while(l<r){mid=l+r>>1;if(mid<=1e6 && mid*mid*mid<x)l=mid+1;else r=mid;}return l*l*l==x;
}bool solve(ll a){if(is2(a) || is3(a)){return true;}for(int i=1,p=prime[1],c;i<=cnt && p<=a;p=prime[++i]){if(a%p==0){c=0;while(a%p==0){a/=p;c++;}if(c==1){return false;}}}if(is2(a) || is3(a))return true;else return false;
}int main(){Eular(5000);cin>>T;while(T--){cin>>a;puts((solve(a))?"yes":"no");}return 0;
} 

这篇关于蓝桥云课 数的拆分（数论）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---