ag亚游平台网站开发,wordpress云典,搭建网站的软件,仙居微信网站开发描述
每个正整数都可以分解成素数的乘积#xff0c;例如#xff1a;62*3、2022 *5 现在#xff0c;给定一个正整数N#xff0c;请按要求输出它的因数分解式。
输入描述
输入第一行#xff0c;包含一个正整数N。约定2N10^12
输出描述
输出一行#xff0c;为N…描述
每个正整数都可以分解成素数的乘积例如62*3、2022 *5 现在给定一个正整数N请按要求输出它的因数分解式。
输入描述
输入第一行包含一个正整数N。约定2N10^12
输出描述
输出一行为N的因数分解式。要求按质因数由小到大排列乘号用星号*表示且左右各空一格。当且仅当一个素数出现多次时将它们合并为指数形式用上箭头^表示且左右不空格。
用例输入 1
6
用例输出 1
2 * 3
用例输入 2
20
用例输出 2
2^2 * 5
用例输入 3
23
用例输出 3
23
来源
GESP 五级
这道题就算用O(n)的方法也过不了所以要用O(sqrt(n))这道题的关键就是在这里。
众所周知i*in就是sqrt(n)的时间复杂度那我们就要在其基础上写代码
ACcode
#include bits/stdc.h
using namespace std;long long n;
bool flagfalse,f2;
int main() {cinn;for (int i2;i*in;i){if (n%i0){f21;int cnt0;while (n%i0) n/i, cnt;//O(sqrt(n))O(log2n)O(sqrt(n))if (flagfalse){flagtrue;}else cout * ;if (cnt1){couti^cnt;}else couti;}}if(f20){coutn;}else if(n!1)cout * n;return 0;
}
感谢王大佬提供思路 看了这么久作者也写了这么久能不能点一个赞在收藏一下呢最好的话在点个关注吧
谢谢啦
