首页 > 其他分享 >P1075 [NOIP2012 普及组] 质因数分解

P1075 [NOIP2012 普及组] 质因数分解

时间:2023-09-21 23:13:46浏览次数:44  
标签:因数分解 质数 sqrt 算法 P1075 复杂度 NOIP2012

算法一

根据唯一分解定理,小于 \(n\) 的最大的能整除 \(n\) 的整数一定就是答案,可以暴力枚举。

时间复杂度 \(O(n)\),实际得分 \(60\)。

算法二

发现算法一不能通过的原因是较大的那个质数可能的取值范围太大了。

而较小的那个质数一定小于等于 \(\sqrt n\),我们枚举它即可。

时间复杂度 \(O(\sqrt n)\),实际得分 \(100\)。

标签:因数分解,质数,sqrt,算法,P1075,复杂度,NOIP2012
From: https://www.cnblogs.com/landsol/p/17721204.html

相关文章

  • [NOIP2012 普及组] 摆花
    [NOIP2012普及组]摆花[NOIP2012普及组]摆花题意有\(n\)个数,每种可以选\(0\lex_i\lea_i\)个,问有多少种方法可以使得\(\sum_{i=1}^nx_i=m\)。Solution1.深搜\(dfs\)显然可以先暴力深搜。#include"bits/stdc++.h"usingnamespacestd;constintmaxn=......
  • LeetCode 周赛上分之旅 #46 经典二分答案与质因数分解
    ⭐️本文已收录到AndroidFamily,技术和职场问题,请关注公众号[彭旭锐]和BaguTreePro知识星球提问。学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场LeetCode周赛的解题报告,一......
  • P1082 [NOIP2012 提高组] 同余方程
    转载自这里问题转化题目问的是满足\(ax\bmodb=1\)的最小正整数\(x\)。(a,b是正整数)但是不能暴力枚举\(x\),会超时。把问题转化一下。观察\(ax\bmodb=1\),它的实质是\(ax+by=1\):这里\(y\)是我们新引入的某个整数,并且似乎是个负数才对。这样表示是为了用扩展欧几里......
  • 82 贪心 [NOIP2012 提高组] 国王游戏
    视频链接: LuoguP1080[NOIP2012提高组]国王游戏#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;structnode{inta,b;booloperator<(node&t){returna*b<t.a*t.b;}}......
  • NOIP2012提高组初赛易错题解析
    一.3. 错误原因:忘记了解析:Intel是全球最大的CPU厂商,AMD是世界上首个研发出7纳米CPU的厂商 6.错误原因:忘记了解析:ENIAC是世界上首台计算机,属于第一代计算机,即电子管计算机 10.错误原因:选项理解错误解析:A由蝙蝠,发明雷达是正确的,B因特网的发明与蜘蛛网无关,只是形......
  • Codeforces Round 885 (Div. 2)E. Vika and Stone Skipping(数学,质因数分解)
    题目链接:https://codeforces.com/problemset/problem/1848/E 大致题意: 打水漂,某人在海岸线以f(正整数)的力量扔出石头,会在f,f+(f-1),f+(f-1)+(f-2),........,f+(f-1)+.....+2+1,的位置接触水面; 现在给出坐标x和q次询问,每次询问给出一个y值,将x=x*y;假设石头在x的位置接触水面,问有多少......
  • [NOIP2012 普及组] 寻宝
    思路:模拟必须mod20123,不然就有可能会爆掉!AC代码#include<iostream>#defineintlonglongusingnamespacestd;boolwhether[10001][101];ints[10001][101],T[10001];signedmain(){ intn,m,S,w,ans=0; cin>>n>>m; for(inti=0;i<n;i++) { for(intj=......
  • 分治/质因数分解 POJ1845 求pow(a, b)的所有约数之和
    //POJ1845求pow(a,b)的所有约数之和//方法:1,分解质因数,将a分解成p1^k1*p2^k2^...*pn^kn//2,那么pow(a,b)为p1^(k1*b)*p2^(k2*b)^...*pn^(kn*b)//3,对于单独的pi^(ki*b),他所有的约数为(1,pi,pi^2,pi^3.....pi^(ki*b));//4,那么整个式子来说,pow(a,......
  • PHP质因数分解,的啊质数乘以大质数逆运算
    <?php$int=97*997;if(!is_int($int)||$int===0){//32位INT最大值2147483647,64位INT最大值9223372036854775807echo"积太大,算不过来!";die;}if($int<=2){echo$int."=".$int;die;}$result=$int.'=&#......
  • [NOIP2012]Vigenère 密码
    题目链接https://ac.nowcoder.com/acm/contest/19306/1052题目分析根据题目给的图发现,密文的会因为密钥的起始位置去偏移,形成了一个环。所以只要我们知道密钥的起始位置,密钥与密钥的距离(密文-密钥),就可以求出明文的位置。AC代码#include<iostream>usingnamespacestd;......