[Swust OJ 217]--Factor(数论,类素数表)
2024-08-21 21:07:29
题目链接:http://acm.swust.edu.cn/problem/0217/
Time limit(ms): 2000 Memory limit(kb): 65535
Description
给定一个数,如N=10,我们知道它有如下4个因子:1、2、5、10。现在的问题来了:给你一个区间[A,B],通过编程求出该区间内具有最多因子的那个数,如果有多个具有最多因子的数,输出最小的那个数。
Input
首先输入一个数cas,代表下面共有cas组测试数据。(cas< =20)
对于每组数据输入一个区间[A,B]其中(1< =A< =B< =1000000)
对于每组数据输入一个区间[A,B]其中(1< =A< =B< =1000000)
Output
输出满足条件的那个数。
Sample Input
2
2 6
20 200
|
Sample Output
6
180
|
解题思路:在判断一个数是否是素数时,我们就已经知道一个数x的因子是不会大于√x,这里算上本生(除去平方之外,每一个i*j增加两个因子),
按照打素数表的思路,i,j,循环i*i<max,i*j<maxn为界
dp[i*i]+=1(两个相同因子),dp[i*j]+=2,然后在给定区间最大值找max_dp,输出下标即可~~~
代码如下:
#include <stdio.h>
using namespace std;
int dp[];
void init(){
for (int i = ; i*i <= ; i++){
dp[i*i] += ;
for (int j = i + ; i*j <= ; j++){
dp[i*j] += ;
}
}
}
int main()
{
init();
int t, l, r;
scanf("%d", &t);
while (t--){
scanf("%d%d", &l, &r);
int ans = l;
for (int i = l; i <= r; i++){
if (dp[i] > dp[ans])
ans = i;
}
printf("%d\n", ans);
}
return ;
}
最新文章
- C#实现微信开发前奏
- Java类WebServer及中间件拿webshell方法总结
- 神奇的GO语言:空接口(interface)
- U盘10分钟安装linux系统
- Ubuntu输入密码登陆后又跳回到登录界面
- (二)list或set的遍历
- [BILL WEI]SQL 如何将查询到的列作为表名去查询数据
- 用WebBrowser实现HTML界面的应用和交互 good
- POJ 1724 ROADS(bfs最短路)
- Android两个注意事项.深入了解Intent和IntentFilter(两)
- js导航栏样式变换
- ORACLE里锁有以下几种模式,v$locked_object,locked_mode【转】
- JQuery使用和选择器
- Java内存模型知识点小结---《深入理解Java内存模型》(程晓明)读书总结
- hibernate添加数据时Exception in thread ";main"; org.hibernate.PropertyValueException: not-null property references a null or transient value: com.javakc.hibernate.test.entity.TestEntity.testName
- js 判断所选时间(或者当前时间)是否在某一时间段的实现代码
- idea搭spring boot项目
- ArrayList 初探
- SpringMVC: web.xml中声明DispatcherServlet时一定要添加load-on-startup标签
- ASP.NET MVC学习之Log4Net配置(日志记录)