Math
2022/7/11 23:22:35
本文主要是介绍Math,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目大意:
JATC的数学老师为了不让同学们感到厌倦,总是出一些有趣的题目。今天的题目是这样的:
给定一个整数n,您可以对它进行如下操作:
- 乘以x:把n乘上x(x是任意正整数)。
- 开方:把n的值更新为sqrt{n} (前提是\sqrt{n}必须为整数)。
您可以对这些操作进行零次至任意次。那么n可以达到的最小值是多少 ?达到最小值需要进行操作的次数又是多少?
显然,班里没有同学能够解决这个问题,您能够帮帮他吗?
题解:
一开始确实没什么头绪。。。。但是当把样例里面的n进行质因数分解后,再与答案进行对比,有了奇怪的发现。
首先把一个数分解为a^x1 * b^x2 * c^x3 * ......d^ x..其中a,b,c....等数都为质数,显然,这些质数是不能通过开方运算来消除的,因此,所能得到的最小数就是这些质数相乘的结果。
解决了最小数的问题,那么怎么得到最少的步数呢?由于是开方运算,每开一次方,所有质数的质数都除以二,我们最终的目标是把所有质数的质数都降为1,所以通过一次乘法将所有质数的指数都变为2^y是一定要做的,所得到的y,加上你做的一次乘法就是步数
具体的步骤
- 对原数进行质因数分解,找到能得到的最小的数
- 检查每个质数的次数是否都为2^y,否则会进行一次乘法,步数在y的基础上加一
- 输出答案
点击查看代码
#include<bits/stdc++.h> using namespace std; bool vis[10000005]; vector<int> prime; struct num{ int n,t; num(){} num(int nn,int tt){ n = nn; t = tt; } };//记录分解后每个质数及其次数,n为该质数 vector<num> divv; int m; int x(){//求得最小的y int now = 1; int tim = 0; while(now < m){ now *= 2; tim++; } return tim; } int main(){ int d; cin >> d; if(d == 1){//特殊情况特殊处理 cout << 1 << " 0" ; return 0; } for(int i = 2; i <= 1000005; i++){//线性筛法,得到数据范围内的质数,便于质因数分解 if(!vis[i]){ vis[i] = 1; prime.push_back(i); } for(int j = 0; j < prime.size(); j++){ if(i * prime[j] > 1000005)break; vis[i * prime[j]]= 1; if(i % prime[j] == 0)break; } } int cnt = 0,time = 0; while(1){ if(d % prime[cnt] == 0){ d /= prime[cnt]; time++; } else{ if(time != 0)divv.push_back(num(prime[cnt],time));//质因数分解并做记录 cnt++; time = 0; } if(d == 1 && time == 0)break; } int ans = 1; bool flag = 1; for(int i = 0; i < divv.size(); i++){//检查一下是否需要进行一次乘法 if(i >= 1){ if(divv[i - 1].t != divv[i].t)flag = 0;//如果不能做到任意两个质数之间的次数相等,那么需要做一次乘法,先做一个标记 } ans *= divv[i].n; m = max(m,divv[i].t); } int g = pow(2,x()); if(g == m && flag){ cout << ans << " " << x(); } else if(g > m || !flag){//如果有质数之间的次数不相等或者所有质数的次数相等但不是2^y这样的形式,就需要做一次乘法 cout << ans << " " << x() + 1; } }
这篇关于Math的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?