网站推广外贸,查询网站怎么做的,考研资料找微信hyhyk1推广可以,建设银行如何进行网站冻结题目描述#xff1a;
一个整数 a 是一个完全平方数#xff0c;是指它是某一个整数的平方#xff0c;即存在一个整数 b#xff0c;使得 ab^2。
给定一个正整数 n#xff0c;请找到最小的正整数 x#xff0c;使得它们的乘积是一个完全平方数。
输入格式#xff1a;
输…题目描述
一个整数 a 是一个完全平方数是指它是某一个整数的平方即存在一个整数 b使得 ab^2。
给定一个正整数 n请找到最小的正整数 x使得它们的乘积是一个完全平方数。
输入格式
输入一行包含一个正整数 n。
输出格式
输出找到的最小的正整数 x。
数据范围
对于 30% 的评测用例1≤n≤1000答案不超过 1000。 对于 60% 的评测用例1≤n≤1e8答案不超过 1e8。 对于所有评测用例1≤n≤1e12答案不超过 1e12。
输入样例1
12输出样例1
3输入样例2
15输出样例2
15
分析步骤 第一分析思路 这道题目题意很简单了就是要我们求出哪一个数相乘是完全平方数。我们先想想什么是完全平方数题目中说是指它是某一个整数的平方即存在一个整数 b使得 ab^2。我们初中也学过无论是什么数都可以拆分成很多质因子的指数的乘积所以呢我们就把这个数拆开成质因子的指数的乘积看看哪一个质因子不是偶数个那么我们就得把这个数乘上直到使得这个质因子的指数都是偶数的时候就代表它可以拆开成另一个数的平方。这个思路极其巧妙大家可以看一看提升一下自己的思维面。 第二书写主函数构建整体框架 输入值定于res让它去乘上那些指数是奇数的值。 我们用for循环从2开始因为2是最小的质因子。 如果i是n的质因子的话就进入while循环将i这个质因子除干净记录一下有几个这样的i如果是奇数个的话我们就得让res去乘上i如果已经是偶数的话就不用去乘。 最后我们经过for循环之后的n如果是大于1的话就代表这也是一个质因子且只有它自己我们还得乘上这个东西。最后输出出来就可以得出答案了。
int main()
{LL n;cin n;LL res 1;for (LL i 2; i * i n; i )if (n % i 0){int s 0;while (n % i 0) s , n / i;if (s % 2) res * i;}if (n 1) res * n;cout res endl;return 0;
} tip这道题思路还有很多但这个思路真的比较巧妙而且速度也极快。大家可以学学
代码
#include iostream
#include cstring
#include algorithmusing namespace std;typedef long long LL;int main()
{LL n;cin n;LL res 1;for (LL i 2; i * i n; i )if (n % i 0){int s 0;while (n % i 0) s , n / i;if (s % 2) res * i;}if (n 1) res * n;cout res endl;return 0;
}
