首页 > 其他分享 >CSP历年复赛题-P1075 [NOIP2012 普及组] 质因数分解

CSP历年复赛题-P1075 [NOIP2012 普及组] 质因数分解

时间:2024-05-30 17:33:13浏览次数:25  
标签:因数分解 int sqrt 因子 P1075 CSP NOIP2012

原题链接:https://www.luogu.com.cn/problem/P1075

题意解读:求n的两个素因子中较大的一个。

解题思路:

数论的简单题,关键在于要知道一定有一个素因子不超过sqrt(n),而另一个素因子必然大于或等于sqrt(n),这样才能减少枚举时间。

100分代码:

#include <bits/stdc++.h>
using namespace std;

int n;

int main()
{
    cin >> n;
    for(int i = 2; i * i <= n; i++)
    {
        if(n % i == 0) 
        {
            cout << n / i;
            break;
        }
    }
    return 0;
}

 

标签:因数分解,int,sqrt,因子,P1075,CSP,NOIP2012
From: https://www.cnblogs.com/jcwy/p/18222850

相关文章

  • P1077 [NOIP2012 普及组] 摆花
    P1077[NOIP2012普及组]摆花题目描述小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共m盆。通过调查顾客的喜好,小明列出了顾客最喜欢的n种花,从1到n标号。为了在门口展出更多种花,规定第i种花不能超过a[i]盆,摆花时同一种花放在一起,且不同种类的花需按标号的......
  • 「NOIP2012」同余方程 题解!!
    嗨嗨嗨!又是我想写这道题,我们就需要掌握:拓展欧几里得顾名思义,它就是欧几里得算法(人话:辗转相除法)的proMax版本别告诉我你不会辗转相除法拓展欧几里得的作用是求对于方程\[a*x+b*y=gcd(a,b)\]解出x,y的值。让我们一步步分析!贴个辗转相除板子先:voidojld(inta,intb){ i......
  • 洛谷题单指南-动态规划1-P1077 [NOIP2012 普及组] 摆花
    原题链接:https://www.luogu.com.cn/problem/P1077题意解读:n种花选m个的选法,每种花数量为ai。解题思路:设dp[i][j]表示前i种花选j个的选法对于第i种花,可以选0,1,2...min(ai,j)个则有递推式:dp[i][j]=∑dp[i-1][j-k],k取0,1,2...min(ai,j)初始化dp[0][0]=1100分代码:#incl......
  • P1077 [NOIP2012 普及组] 摆花
    题目:链接:https://www.luogu.com.cn/problem/P1077总的来说就是和上题差不多?记dp[i][j]为前i种花塞进了j的背包的种类,那么状态转移方程:就是:dp[i][j]=dp[i-1][j]+dp[i-1]j-k贴代码:#include<iostream>#include<vector>#include<algorithm>#include<math.h>#include<ss......
  • P1075 [NOIP2012 普及组] 质因数分解
    P1075[NOIP2012普及组]质因数分解[NOIP2012普及组]质因数分解题目描述已知正整数\(n\)是两个不同的质数的乘积,试求出两者中较大的那个质数。输入格式输入一个正整数\(n\)。输出格式输出一个正整数\(p\),即较大的那个质数。样例#1样例输入#121样例输出#1......
  • P1083 [NOIP2012 提高组] 借教室
    题目链接:本题由于是对某一段区间的数统一进行删除某个数的操作,很容易想到差分。对于能否二分,有一个界定标准:状态的决策过程或者序列是否满足单调性或者可以局部舍弃性。在本题中,由于随着订单数量的增加,每天可用教室的数量一定单调下降。也即,如果前一份订单都不满足,那么之后的所......
  • 洛谷题单指南-贪心-P1080 [NOIP2012 提高组] 国王游戏
    原题链接:https://www.luogu.com.cn/problem/P1080题意解读:通过不同的排队方式,让获得最多奖赏的大臣金额尽可能的少。此题如果没有思路,用全排列枚举可以“骗”分,更好的做法直觉上是某种贪心策略,另外基于数据规模考虑,要拿满分,需要上高精度。下面就由浅入深一步一步的解决。解题思......
  • P1082 [NOIP2012 提高组] 同余方程
    原题链接扩展欧几里得算法的应用,关于原理性的讲解这里就略去了,这边给出学习链接即模板。intexgcd(inta,intb,int&x,int&y){if(b==0){x=1;y=0;returnx;}intd=exgcd(b,a%b,x,y);x=y;y=d-a/b*y;returnx;}文......
  • [NOIP2012 提高组] 借教室
    原题链接一道二分+差分的题目,作为学习前缀和和差分的引入题目非常合适。首先检验其单调性,如果一个申请人订单不用修改,那么其前面的申请人也不用修改,符合单调性。接着,这道题暴力的思路就很简单,但是看到运算量(n,m高达1e6),暴力的时间复杂度为O(n*m)显然超时。那么就是运用差分思想......
  • 大数因数分解Pollard_rho
    大数因数分解Pollard_rho#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<map>usingnamespacestd;constinttimes=50;intnumber=0;map<long......