pat 1096（patekphilippe手表）

pat 1096（patekphilippe手表）

1、题目链接 https://patest.cn/contests/pat-a-practise/1096 2、题意分析 （1）题意：给出一个数字，找出其连续最长的因子序列 （2）分析：暴力破解即可。 3、思想 （1）我们设想，对于数字630 = 2 * 5 * 6 * 7；但是我们一般都存在一个误区，就是说， 我们该怎么存储子序列的最大长度呢？例如：对于因子2，其子序列长度为1,但是到了因子5的时候，子序列长度也为1，但是这个时候我们该保留哪一个子序列呢？ （2）针对上述问题，以及因子本身的性质（一个数的因子是固定不变的），所以说我们从2,开始遍历与从5，或者6,7开始遍历都是一样的。即：我们（1）遍历2-sqrt(number),将其连乘序列数放到数组中（2）比较数组大小，挑出数值最大的， 起始值相对较小的（3）结束 即可。 4、源代码 #include #include #define size 10000 int main(){ int number; scanf("%d",&number); int i ; int array[size]={0},tempPro;//数组array[]用来存储长度，temp用来存储当前可以除尽number的数i int tempNum ; int primeFlag = 1; for(i = 2;i <= sqrt(number);i++){ tempNum = number;//暂存number的值 if(tempNum % i == 0 ){//如果说能够除尽 primeFlag = 0; //素数标志 array[i] ++;//代表连续乘值加1 tempPro = i; tempNum /= i;//更新 int j = i+1; while(tempNum != 0){//直到除尽 if(tempNum % j == 0){//如果能够将j整除 if(j == 1 + tempPro){//如果连续 array[i]++; //长度加1 tempPro = j;//更新tempPro值 tempNum /= j; } else break; } else break;//跳出循环 j++;//j往后加1 } } } if(primeFlag){ printf("1\n%d",number); return 0; } int max = 0,k;//k是用来记录i值 for(i = 2;i < sqrt(number) ;i++){ // printf("%d ",array[i]); if(array[i] > max){ max = array[i]; k = i; } } printf("%d\n",array[k]); int m = k; while(array[k]-- > 0){ printf("%d",m); if(array[k]!=0){ printf("*"); } m++; }printf("\n"); } /* 630 */4、坑点 （1）这里注意素数的情况，对应测试点可以找一个素数尝试。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。