kuangbin专题十四 LightOJ1220 分解质因数

2024-02-02 08:32

本文主要是介绍kuangbin专题十四 LightOJ1220 分解质因数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:
给你一个数n = b^p,求p的最大值。
题解:
分解质因数,一开始我以为是找到x = p1^x1*p2^x2*p3^x3*…*pk^xk中指数的最大值,后来我错了。。原来是要找他们的最大公约数,ORZ,因为n = b^p是由一个数和一个指数组成的,所以相当于要求出他们所有的指数的最大公约数得出一个数b,例如6=2^1*3^1应该是得到6=6^1吧,为什么呢?因为gcd(2,3)=1…然后这道题还有个坑点,导致我WA的不成人样,n的范围为有符号的32位。。然后我就当int范围来作死了,殊不知,int有符号31位,所以要用long long int,最后这道题还有一点就是,如果n为负数的话就用将求出来的指数p变成奇数,因为偶数是不可能得出负数的。。所以要将p不断/2,就相当于b不断*2.然后将p变成奇数输出就可以了。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int MAXN=1e6+7;
bool prime[MAXN];
int a[MAXN/10],m=0;
void Prime()
{prime[0]=prime[1]=false;prime[2]=true;for(int i=3;i<MAXN;i++){if(i%2) prime[i]=true;else prime[i]=false;}for(int i=2;i<=sqrt(MAXN);i++){if(prime[i])for(int j=i+i;j<MAXN;j+=i)prime[j]=false;}for(int i=2;i<MAXN;i++)if(prime[i])a[m++]=i;
} 
int gcd(int a,int b)  //求最大公约数  
{  return b?gcd(b,a%b):a;  
}  
int main()
{Prime();int t,k=1;scanf("%d",&t);while(t--){long long int n;bool flag=false;scanf("%lld",&n);if(n<0) n=-n,flag=true;int ans=0;for(int i=0;i<m&&a[i]<=n;i++){int num=0;while(n%a[i]==0){num++;n/=a[i];}if(ans==0)ans=num;elseans=gcd(ans,num);}if(n!=1)ans=1;if(flag){while(ans%2==0)ans/=2;}printf("Case %d: %d\n",k++,ans); }
} 

这篇关于kuangbin专题十四 LightOJ1220 分解质因数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/670101

相关文章

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

音视频入门基础:WAV专题(10)——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础:WAV专题(6)——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道,通过FFprobe命令可以打印WAV音频文件每个packet(也称为数据包或多媒体包)的信息,这些信息包含该packet的pts、dts: 打印出来的“pts”实际是AVPacket结构体中的成员变量pts,是以AVStream->time_base为单位的显

专题二_滑动窗口_算法专题详细总结

目录 滑动窗口,引入: 滑动窗口,本质:就是同向双指针; 1.⻓度最⼩的⼦数组(medium) 1.解析:给我们一个数组nums,要我们找出最小子数组的和==target,首先想到的就是暴力解法 1)暴力: 2)优化,滑动窗口: 1.进窗口 2.出窗口 3.更新值 2.⽆重复字符的最⻓⼦串(medium) 1)仍然是暴力解法: 2)优化: 进窗口:hash[s[rig

hot100刷题第1-9题,三个专题哈希,双指针,滑动窗口

求满足条件的子数组,一般是前缀和、滑动窗口,经常结合哈希表; 区间操作元素,一般是前缀和、差分数组 数组有序,更大概率会用到二分搜索 目前已经掌握一些基本套路,重零刷起leetcode hot 100, 套路题按套路来,非套路题适当参考gpt解法。 一、梦开始的地方, 两数之和 class Solution:#注意要返回的是数组下标def twoSum(self, nums: Lis

十四、我们应当怎样做需求分析:子用例与扩展用例

用例模型作为UML中4+1视图中非常重要的一员,非常集中地体现了面向对象的分析与设计思想。用例模型将现实世界中连续的一个一个业务流程,按照场景划分到了一个一个的用例中。由于场景的出现,使得用例中的业务流程存在着高度的内聚性,从而成为了日后各种对象的雏形。同时,在用例分析中,又将那些存在于各个用例中的,相同或相近的业务操作提取出来,形成一个一个的子用例或扩展用例,又体现了面向对象设计中的复用性。现在

数字电路专题:verilog 阻塞赋值和非阻塞赋值

verilog 阻塞赋值 和 非阻塞赋值 “=”阻塞赋值, ”<=”非阻塞赋值。阻塞赋值为执行完一条赋值语句,再执行下一条,可理解为顺序执行,而且赋值是立即执行; 非阻塞赋值可理解为并行执行,不考虑顺序,在 always 块语句执行完成后,才进行赋值。 如下面的阻塞赋值: //代码如下:module top(din,a,b,c,clk);input din;input clk;out

特征值分解(EVD)和奇异值分解(SVD)—应用于图片压缩

特征值分解(EVD)和奇异值分解(SVD)—应用于图片压缩 目录 前言 一、特征值分解 二、应用特征值分解对图片进行压缩 三、矩阵的奇异值分解 四、应用奇异值分解对图片进行压缩 五、MATLAB仿真代码 前言         学习了特征值分解和奇异值分解相关知识,发现其可以用于图片压缩,但网上没有找到相应代码,本文在学习了之后编写出了图片压缩的代码,发现奇异值分

算法专题一: 双指针

目录 前言1. 移动零(easy)2. 复写零(easy)3. 快乐数(medium)4. 盛水最多的容器(medium)5. 有效三角形的个数(medium)6. 和为 s 的两个数字(easy)7. 三数之和(medium)8. 四数之和(medium) 前言 常见的双指针有两种形式,一种是对撞指针,一种是左右指针。 1. 对撞指针: ⼀般用于顺序结构中,也称左右指针。

【C++STL(十四)】一个哈希桶简单模拟实现unordered_map/set

目录 前言 一、改造哈希桶 改造结点类 改造主体  模板参数改造  迭代器(重点) 改造完整哈希桶 unordered_map模拟实现 unordered_set模拟实现 前言 前面的文章都有说unordered_map/set的底层结构就是哈希表,严格来说是哈希桶,那么接下来我们就尝试使用同一个哈希桶来模拟实现一下。整体的逻辑和一棵红黑树封装map/set类似,所以

《黑神话:悟空》专题合集MOD/修改器/壁纸/音乐/CG剧情

《黑神话:悟空》专题合集」 链接:https://pan.quark.cn/s/d67857f4e308 包含内容: 《黑神话:悟空》MOD合集 《黑神话:悟空》修改器(风灵月影) 《黑神话:悟空》壁纸合集 《黑神话:悟空》3小时CG完整剧情合集 4K120帧最高画质!国语 简中字幕 附:4K 结尾动画合集 ​​​国语 简中字幕 《黑神话:悟空》主题曲 《黑神话