反素数 ,这个问题编程的算法

Problem Description
反素数就是满足对于任意i(0<i<x),都有g(i)<g(x),(g(x)是x的因子个数),则x为一个反素数。现在给你一个整数区间[a,b],请你求出该区间的x使g(x)最大。

Input
第一行输入n,接下来n行测试数据
输入包括a,b, 1<=a<=b<=5000,表示闭区间[a,b].

Output
输出为一个整数,为该区间因子最多的数.如果满足条件有多个,则输出其中最小的数.

Sample Input
3
2 3
1 10
47 359

Sample Output
2
6
240
Hint

2的因子为:1 2
10的因子为:1 2 5 10

0

2个回答

0

伪代码,应该可以看懂

y=int[5001]
//第一步,计算5000以内所有数的因子个数,50的因子个数是y[50]
for(int i=1;i<=5000;i++)
口for(int j=1;j<=i;j++)
口口if(i%j==0)y[i]+=1;

//第二步查找区间[a,b]最大值,下面提高效率最低的查找o(n)
n=read(n);
for(i=0; i<n ; i++ ) {

口a=read(a);
口b=read(b);
口maxindex=b;
口for(int j=b-1;j>=a;j--){
口口if(y[maxindex]<y[j])maxindex=j;
口print(maxindex);

}

0
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
反素数 ,这个问题编程的算法
Problem Descriptionrn反素数就是满足对于任意i(0
桃子的算法笔记——反素数详解(acm/OI)
做了POJ2286之后,发现题目要求求出1-n因数最大的那个数。当时没想到合适的方法,后来想到了是反素数。 顺便总结了常见的和反素数有关的题型(个人觉得反素数只是作为题目的某一部分出现),还请各位dalao轻拍。   其实顾名思义,素数就是因子只有两个的数,那么反素数,就是因子最多的数(并且因子个数相同的时候值最小),所以反素数是相对于一个集合来说的。 我所理解的反素数定义就是,在一个集合...
【HDU4392】【反素数强大的模版 java或者C++】
传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4392 JAVA版本: import java.io.BufferedInputStream; import java.math.BigInteger; import java.util.ArrayList; import java.util.HashMap; import java.
反素数深度分析
今天要我要讲的是反素数,在ACM中也算是常见的考点,那么对于搞ACM的同学来说,很有必要搞清楚它,所以接下 来我会很详细地讲解。   在讲解反素数之前,我们先来看反素数的概念。   反素数的定义:对于任何正整数,其约数个数记为,例如,如果某个正整数满足:对任意的正整             数,都有,那么称为反素数。   从反素数的定义中可以看出两个性质:   (1)一个反素数
素数系列——反素数
Emirp Time Limit: 5000 MS Memory Limit: 100000 K Total Submit: 147(60 users) Total Accepted: 61(55 users) Rating: Special Judge: No Description An
反素数求解及相关题目
反素数定义:对于任何正整数n,其约数个数记为f(n),例如f(6)=4;如果存在一个正整数n满足:对于任意的正整数x(0&amp;lt;x&amp;lt;n),都有f(x)&amp;lt;f(n)成立,那么把n称为反素数。一个反素数的所有质因子必然是从2开始的若干个质数,因为一个数是反素数,说明在跟它约数相同的数中,它是最小的。如果n=2t1 * 3t2 * 5t3 *...,那么一定有t1&amp;gt;=t2&amp;gt;=t3&amp;...
反素数(其实重点不是反素数。。。)
初学反素数的时候总会感到很迷茫,因为网上你找来找去只有ACdreamer一个版本的博客。我查阅了很多资料,也问过几位学长,才知道,重点不是反素数。 \\ 怎么说呢,你不能把反素数当成卡特兰数这种以数为中心的东西,其实反素数在我看来更像是一种数论。关键不是去求这个反素数,而是靠反素数的定义带来的思想做题。 反素数 #define Y(i) i的因数的个数 我们把n称为反...
打表练习题——反素数
题目描述 如果一个自然数比所有比它小的自然数的约数个数都要多,那么我们就称这个数为一个反素数。例如,1、2、4、6、12和24都是反素数。 任务: 请写一个程序: 读入一个自然数n; 找出不大于n的最大的反素数; 将结果输出。 本题需要用到的知识:约数个数定理 代码(不会打表没逼逼) //By Bibi /// .-~~~~~~~~~-._ ...
反素数打表
//#include&amp;lt;bits/stdc++.h&amp;gt; #define _CRT_SBCURE_NO_DEPRECATE #include &amp;lt;set&amp;gt; #include &amp;lt;map&amp;gt; #include &amp;lt;cmath&amp;gt; #include &amp;lt;queue&amp;gt; #include &amp;lt;stack&amp;gt; #include &amp;lt;vector&amp;gt;
java语言程序设计基础篇——素数(方法)
1. 回文素数回文素数是指一个数同时为素数和回文数。编写程序,显示前100个回文素数,每行显示10个数并且准确对齐。①构造方法boolean isPrime(int number)判断一个数是否为素数,若是则返回true,若不是,则返回false②构造方法boolean isPalindrome(int number)判断一个数是否是回文数,若是则返回true,若不是则返回false③若同时满足i...
Python编程 判断和输出素数的多种方法
1.for循环输出100以内的素数 def get_prime_scope(scope=100): numlist = [] i = 2 for i in range(2, scope + 1): j = 2 for j in range(2, int(math.sqrt(i))): if (i % j == 0): ...
PTA 输出前n个素数
#include &lt;stdio.h&gt; // 函数功能:输出前n个素数 int isPrime( int num ) ; // 函数声明 int main(void) { int n; scanf("%d", &amp;n); printf("需要输出前%d个素数。\n", n); printf("前%d个素数如下所述:\n", n); ...
[POI2002][HAOI2007]反素数 数论 搜索 好题
题目描述: 对于任何正整数x,其约数的个数记作g(x)。例如g(1)=1、g(6)=4。 如果某个正整数x满足:g(x)&amp;gt;g(i) 0&amp;lt;i&amp;lt;x,则称x为反质数。例如,整数1,2,4,6等都是反质数。 现在给定一个数N,你能求出不超过N的最大的反质数么? 题解: 显然,我们要求的是 $[1,N]$ 中约数个数最多且该数字最小的值。 根据约数个数公式:$ans=(p_{1}...
反素数()
void dfs(int dept,LL nn,LL fnum,int index) { if(fnum>k)return ; ///if(nn>Linf) return ; if(fnum==k&&ans>nn) ans=nn; for(int i=1; i<=index; i++) { if((ansk))
反素数——Antiprime
描述 如果一个大于等于 1 的正整数 n ,满足所有小于 n 且大于等于 1 的所有正整数的约数个数都小于 n 的约数个数,则 n 是一个 Antiprime 数。譬如:1,2,4,6,12,24 ,它们都是 Antiprime 数。 请你计算不大于 n 的最大 Antiprime 数。 输入 一行一个正整数 n 。 输出 只包含一个整数,即不大于 n 的最大 Antiprime 数。 样例输入...
反素数 Anti-prime number知识总结
定义 对于任何正整数x,其约数的个数记作g(x)。 e.g. g(1)=1、g(6)=4。 如果某个正整数x满足:g(x) &amp;amp;gt; g(i) (0 &amp;amp;lt; i &amp;amp;lt; x),则称x为反质数。————摘选自《百度百科》 性质 一个反素数的质因子必然是从2开始连续的质数。 p=2^t1*3^t2*5^t3*7^t4……必然t1≧t2≧t3≧t4≧…… 证明 (p为约数个数一定...
反素数专题
今天要我要讲的是反素数,在ACM中也算是常见的考点,那么对于搞ACM的同学来说,很有必要搞清楚它,所以接下 来我会很详细地讲解。   在讲解反素数之前,我们先来看反素数的概念。   反素数的定义:对于任何正整数,其约数个数记为,例如,如果某个正整数满足:对任意的正整             数,都有,那么称为反素数。   从反素数的定义中可以看出两个性质:   (1)一个反素数
【题目整理】反素数
目录 Codeforces27E Number With The Given Amount Of Divisors(模板题) zoj 2562 More Divisors(模板题) Codeforces27E Number With The Given Amount Of Divisors(模板题) 【题意】 给定一个数,求一个最小的正整数,使得的约数个数为。 【解题思路】 模板题。...
【原创】(一)用Python玩转初等数论之质数
目录 (一)用Python玩转初等数论之质数 一、数论相关内容及文章声明 本系列文章讲些啥 数论是啥? 初等数论又是啥 质数又是啥? 阅读本篇文章需要的知识 同余 取模 整除 在Python中基本的除法有三种,分别是除、取模、取整除 二、进入正题——如何判断质数 法-1 定义-1 程序-1 法-2 定义-2 程序-2 三、准备进阶——生成素数 以程序-2为基本算法 埃拉托斯特
有趣的积水问题(Twitter编程面试题)
以下内容来自转载: Twitter面试题:水沟积水问题 问题描述:“看下面这个图片” “在这个图片里我们有不同高度的墙。这个图片由一个整数数组所代表,数组中每个数是墙的高度。上边的图可以表示为数组[2,5,1,2,3,4,7,7,6]” “假如开始下雨了,那么墙之间的水坑能够装多少水呢?” 思路分析: 一种只需要一次遍历的方法(注:不知道算不算动态规划算法
反素数学习
原始链接: ACdreamers: 反素数深度分析 反素数的定义:对于任何正整数,其约数个数记为,例如,如果某个正整数满足:对任意的正整             数,都有,那么称为反素数。   从反素数的定义中可以看出两个性质:   (1)一个反素数的所有质因子必然是从2开始的连续若干个质数,因为反素数是保证约数个数为的这个数尽量小 (2)同样
【ZOJ 1562和 BZOJ 1053】【反素数】【求n以内的因子最多的那个数(即不超过n的最大反素数)】
传送门1:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1562  传送门2:http://www.lydsy.com/JudgeOnline/problem.php?id=1053 ZOJ1562题意:求n以内的因子最多的那个数 BZOJ1053题意:不超过n的最大反素数(这题数据稍小) 反素数讲解:
python实现反向数,回文数,回文素数,反素数,梅森素数,双素数。
利用python3实现求一个数的反向数;判断一个数是否是回文数;判断是否是回文素数,反素数,梅森素数,双素数。
1060 最复杂的数 (反素数)
1060 最复杂的数  题目来源: Ural 1748 基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题  收藏  关注 把一个数的约数个数定义为该数的复杂程度,给出一个n,求1-n中复杂程度最高的那个数。 例如:12的约数为:1 2 3 4 6 12,共6个数,所以12的复杂程度是6。如果有多个数复杂度相等,输出最小的。 Input 第1行:一...
[JSOI2016]反质数序列
题目大意在一个序列里选出一个最长子序列,使得序列中任意两个数相加均不为质数。最大独立首先序列里不可能出现多于1个1,所以多个1可以只保留1个。 那么接下来对于任意的ai+aj=p1,aj+ak=p2(p1,p2为质数),都有p1,p2不为2,也就是p1,p2都是奇数。通过奇偶性分析可以得到ai+ak不为质数。 所以可以根据奇偶性黑白染色,然后两个数相加为质数就连一条边,对建出的二分图求最大独立即
Josephus问题求解
/**//************************************************************************Josephus问题求解:    设有n个人围坐一个圆桌周围,,现从第S人开始报数,数到第m的人出列,    然后从出列的下一个重新开始报数,数列的第m个人又出列……如此重复,直    到所有的人全部出列为止。对任意给定的n、s、m,求按出列
URAL 1748 The Most Complex Number 【区间最大反素数(模板)】
1748. The Most Complex Number Time limit: 1.0 second Memory limit: 64 MB Let us define a complexity of an integer as the number of its divisors. Your task is to find the most complex intege
线段树 + 反素数 poj2886
关于反素数:摘自此博客:http://magicode.blog.sohu.com/120450550.html 这个题主要用到线段树的思想,每次推算出要出去的人在当前剩下的人中的排位,再用线段树求出其原来的编号,即可算出每次应该出去的人,该人得到的糖果数为f(p)(p为出去的顺序,f(p)为p约数的个数 其实当总人数n确定时,p的值和f(p)的值就确定了,p为小于等于n的最大反素
[HAOI2007]反素数ant题解
题目链接 分析 感觉这道题就是一道披着数论外衣的搜索 我们可以推出三个性质 1.最大反素数即为范围内因数最多的最小的那一个 2.最多有10个素因子,且素因子的幂不超过31 3.必定是最小的几个素因子相乘,且指数非严格递减 2可根据数据范围推出,最小的10个素数相乘大于2^31,所以可知。对于3,我们可根据唯一分解定理分析得出。这样搜索即可 时间:0ms。 上代码 #incl...
说说算法题的那些事儿(3)~麻将算法题
麻将,风靡大江南北,今儿让笔者和大家一起看看麻将中的算法题 中国麻将(Chinese Mahjong, UVa 11210) 麻将是一个中国原创的4人玩的游戏。这个游戏有很多变种,但本题只考虑一种有136张牌的玩法。 这136张牌所包含的内容如下。 饼(筒)牌:每张牌包括一系列点,每个点代表一个铜钱,如图所示。本题中用1T、2T、3T、4T、5T、6T、7T、8
求反素数
问题描述: 对于任何正整数x,起约数的个数记做g(x).例如g(1)=1,g(6)=4. 如果某个正整数x满足:对于任意i(0 现在给一个N,求出不超过N的最大的反素数. 比如:输入1000  输出 840 思维过程: 求[1..N]中约数在大的反素数-->求约数最多的数 如果求约数的个数 756=2^2*3^3*7^1 (2+1)*(3+1)*(1
杭电2521 反素数
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n=sc.nextInt(); while (n-->0) {
POJ 2034 反素数,素数筛选,DFS暴力搜索
输入S,T,D,输出从S到T的某种排列中长度不超过D的连续和都为合数,输出其中的一种排列,否则输出没有。。。。 #include #include #include const int maxn=1000+10; using namespace std; bool pri[maxn*maxn],p[maxn]; int list[maxn]; int s,t,d; void ss(){ fo
【洛谷1463】[POI2002] [HAOI2007] 反素数(打表)
点此看题面 大致题意:定义g(x)g(x)g(x)为正整数xxx的约数个数,一个反质数xxx满足对于任意一个i(0&amp;amp;amp;amp;amp;lt;i&amp;amp;amp;amp;amp;lt;x)i(0&amp;amp;amp;amp;amp;lt;i&amp;amp;amp;amp;amp;lt;x)i(0g(i)&amp;amp;amp;amp;amp;lt;g(x)g(i)&amp;amp;amp;amp;amp;lt;g(x)g(i)nnn,请你求出不大于nnn的最大的反质数。
编程5大算法总结--概念加实例
分治法,动态规划法,贪心算法这三者之间有类似之处,比如都需要将问题划分为一个个子问题,然后通过解决这些子问题来解决最终问题。但其实这三者之间的区别还是蛮大的。 贪心是则可看成是链式结构 回溯和分支界限为穷举式的搜索,其思想的差异是深度优先和广度优先 一:分治算法 一、基本概念 在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两
进程同步互斥——读者写者问题
经过几天的尝试与努力,初步实现了操作系统实验设计三个题目中最简单的一个:编程模拟进程的同步与互斥。真是煞费苦心。没有可视化的操作界面,完全用C/C++来进行模拟,着实难受。 在自己对同步互斥的理解的基础上,借鉴别人的一些实现方法,终于将代码初步敲打出来。代码不多,却也复杂。下面简单对程序做下介绍。 (一)实验目的 进一步理解 “临界资源” 的概念; 把握在多个进程并发执行过
poj2886线段树+反素数
题意: N个小朋友围一圈。 指定一个人为起始点之后,此人出圈。 按照这个人手中卡片的数字找到下一个人,下一个人出圈。 。。。 知道最后一个人出圈。 思路: 一:当期指定的人在第K个位置,他出圈后,找到下一个人在剩下的人中的位置next_K。 if(A >= 0) next_k = (k-1+A-1)%n + 1; else next_k = ((k-1
数论常用内容——反素数
提到反素数,大家可能比较陌生,这里博主我对反素数的了解也不是很深刻,希望能借此机会来总结一下并和大家交流概念对于任何正整数n,其约数个数为f(n),如果某个正整数n满足:对任意正整数i(0<i<n),都有f(i)<f(n),那么称n为反素数。 性质性质1、一个反素数的所有质因子必然是从2开始的连续若干个质数,因为反素数是保证约数个数为x的这个数n尽量小性质2、如果n=2^t1*3^t2*5^t3*…
[bzoj3085]反质数加强版SAPGAP【暴力】【数论】
【题目描述】   http://www.lydsy.com/JudgeOnline/problem.php?id=3085 【题解】   这题同[bzoj1053]但数据范围更大,单纯的高精度不足以通过此题,因此我们要加上更强力的剪枝:   考虑每个质数的更紧的限制:假设现在有iii个PPP,再增加一个花费的代价为PPP利益为(i+1)/i(i+1)/i(i+1)/i。如果当前取了kkk个...
贪心算法——2.4会议安排
         问题描述如上,这是一个典型的会议安排问题,会议安排的目的是在有限的时间内召开最多的会议(任何两个会议不能同时进行)。每一个会议都有起始时间bi和结束时间ei且bi&amp;lt;ei,即一个会议的进行时间为半开区间[bi,ei),如果[bi,ei)和[bj,ej)不相交,则会议i和j相容。 贪心策略有三种选择: 在这里我们选择第三种,其实就是在最短的时间里面开最多的会,...
文章热词 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型 设计制作学习
相关热词 mysql关联查询两次本表 native底部 react extjs glyph 图标 python+自编程学习算法 java的一些学习这个。