hdu 4542 数论 + 约数个数相关 腾讯编程马拉松复赛

时间:2022-06-23 11:02:16

题目:http://acm.hdu.edu.cn/showproblem.php?pid=4542

小明系列故事——未知剩余系

Time Limit: 500/200 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)

Total Submission(s): 889    Accepted Submission(s): 207

Problem Description
  “今有物不知其数,三三数之有二,五五数之有三,七七数之有二,问物几何?”



  这个简单的谜题就是中国剩余定理的来历。



  在艰难地弄懂了这个定理之后,小明開始设计一些复杂的同余方程组X mod ai = bi 来调戏别人,结果是必定的,都失败了。



  但是在这个过程中,小明发现有时并不一定要把ai和bi告诉你。他仅仅须要告诉你,ai在区间 [1, X] 范围内每一个值取一次时,有K个ai使bi等于0,或有K个ai使bi不等于0,最小的X就能够求出来了。



  你来试试看吧!
 
Input
输入第一行为T,表示有T组測试数据。

每组数据包括两个整数Type和K,表示小明给出的条件。Type为0表示“有K个ai使bi等于0”,为1表示“有K个ai使bi不等于0”。



[Technical Specification]



1. 1 <= T <= 477

2. 1 <= K <= 47777, Type = 0 | 1
 
Output
对每组数据,先输出为第几组数据,假设没有这种数,输出“Illegal”,否则输出满足条件的最小的X,假设答案大于2^62, 则输出“INF”。
 
Sample Input
3
0 3
1 3
0 10
 
Sample Output
Case 1: 4
Case 2: 5
Case 3: 48
 
Source
 

这道题学到了非常多东西。

1、题目意思:如第一问,因子个数>=k就可以,而非一定等于k;

2、对第一问,原来直接copy的CF 27E的代码(參见本博客),果断TLE…

http://blog.csdn.net/u011026968/article/details/25870377

然后看了题解,发现搜索的时候事实上能够直接一次性把答案都搜索完。这就省去了每次查询都搜索的时间。

3、第二问至今不明确为什么能够枚举出来而不会TLE----------求大神不吝赐教

枚举注意预计范围,本题中,一个数n的约数个数,不会超过2*sqrt(n)。

4、学了下把数分解质因数,也做了一个质因数分解的模板,在还有一篇博客http://blog.csdn.net/u011026968/article/details/25949677

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdlib>
using namespace std; #define ll long long
const long long INF = (1LL<<62);
const int MAXN=100010; //int prm[10]={2,3,5,7,11,13,17,19,23,29};
int k;
ll ans1,ans2;
int flag,prm[MAXN+1];
bool is[MAXN+1];
int getprm(int n){
int i, j, k = 0;
int s, e = (int)(sqrt(0.0 + n) + 1);
memset(is, 1, sizeof(is));
prm[k++] = 2; is[0] = is[1] = 0;
for(i = 4; i < n; i += 2) is[i] = 0;
for(i = 3; i < e; i += 2) if(is[i]) {
prm[k++] = i;
for(s = i * 2, j = i * i; j < n; j += s)
is[j] = 0;
// 由于j是奇数,所以+奇数i后是偶数,不必处理!
}
for( ; i < n; i += 2) if(is[i]) prm[k++] = i;
return k; // 返回素数的个数
} ll factor[101][2];
int facnt;
int div(ll x)
{
//ll a=sqrt(x*0.1)+1,tmp=x,num=1,cnt=0,facnt=0;
int num=1;
facnt=0;
ll tmp=x;
for(int i=0;prm[i]<=tmp/prm[i];i++)
{
if(tmp%prm[i] == 0)
{
factor[facnt][0]=prm[i];
factor[facnt][1]=0;
while(tmp%prm[i] == 0)
{
tmp/=prm[i];
factor[facnt][1]++;
}
num*=(factor[facnt][1]+1);
facnt++;
}
}
if(tmp!=1)
{
factor[facnt][0]=tmp;
factor[facnt++][1]=1;
num*=2;
}
return num;
}
long long aa[47787];
void dfs1(int a,int b,ll tmp)
{
if(a>47777)return;
if(tmp<=INF && (aa[a]==0||aa[a]>tmp)){aa[a]=tmp;}
for(int i=1;i<=62;i++)
{
if(tmp>INF/prm[b])break;
tmp*=prm[b];
dfs1(a*(i+1),b+1,tmp);
}
} void solve()/*n的约数的个数不多于2*sqrt(n)*/
{
ll x=1;
while(x*x <= 4*(k+x))
{
ll ans=div(k+x);
if(ans == x)
{
printf("%I64d\n",x+k);
return;
}
x++;
}
printf("Illegal\n");
} int main()
{
int ncase,t;
getprm(MAXN-1);
scanf("%d",&ncase);
memset(aa,0,sizeof(aa));
dfs1(1,0,1);
for(int icase=1;icase<=ncase;icase++)
{ flag=0;
ans1=ans2=INF+1;
scanf("%d%d",&t,&k);
printf("Case %d: ",icase);
//system("pause"); if(!t)
{ if(aa[k]!=0)printf("%I64d\n",aa[k]);
else printf("INF\n");
}
else
{
solve();
} }
return 0;
}

hdu 4542 数论 + 约数个数相关 腾讯编程马拉松复赛的更多相关文章

  1. HDU&lpar;4528&rpar;,BFS,2013腾讯编程马拉松初赛第五场&lpar;3月25日&rpar;

    题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=4528 小明系列故事——捉迷藏 Time Limit: 500/200 MS (Java/O ...

  2. 2013腾讯编程马拉松初赛第〇场&lpar;HDU 4503&rpar; 湫湫系列故事——植树节

    http://acm.hdu.edu.cn/showproblem.php?pid=4503 题目: 已知湫湫的班里共有n个孩子,每个孩子有Bi个朋友(i从1到n),且朋友关系是相互的,如果a小朋友和 ...

  3. HDU 4508 沼泽湿地系列故事——记住减肥I (2013腾讯编程马拉松预赛第一)

    pid=4508">http://acm.hdu.edu.cn/showproblem.php?pid=4508 题目大意: 给定一些数据. 每组数据以一个整数n開始,表示每天的食物清 ...

  4. HDU 4508 湫湫系列故事——减肥记I (2013腾讯编程马拉松初赛第一场)

    http://acm.hdu.edu.cn/showproblem.php?pid=4508 题目大意: 给定一些数据. 每组数据以一个整数n开始,表示每天的食物清单有n种食物.  接下来n行,每行两 ...

  5. 2013腾讯编程马拉松初赛第〇场(HDU 4504)威威猫系列故事——篮球梦

    http://acm.hdu.edu.cn/showproblem.php?pid=4504 题目大意: 篮球赛假如我们现在已经知道当前比分 A:B,A代表我方的比分,B代表对方的比分,现在比赛还剩下 ...

  6. 2013腾讯编程马拉松&vert;&vert;HDU 4505 小Q系列故事——电梯里的爱情 水水水

    http://acm.hdu.edu.cn/showproblem.php?pid=4505 题目大意: 电梯最开始在0层,并且最后必须再回到0层才算一趟任务结束.假设在开始的时候已知电梯内的每个人要 ...

  7. 2013腾讯编程马拉松初赛第一场(3月21日) 湫湫系列故事——减肥记II ----线段树

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=4509 虽然制定了减肥食谱,但是湫湫显然克制不住吃货的本能,根本没有按照食谱行动! 于是,结果显而易见… 但 ...

  8. 2013腾讯编程马拉松初赛第〇场(3月20日)湫湫系列故事——植树节 HDOJ 4503

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=4503 思路:hint from a GOD-COW. 将每一个人模拟成图的一个点,两点连线当且仅当两人是朋 ...

  9. 2013腾讯编程马拉松初赛第二场(3月22日) 小Q系列故事——为什么时光不能倒流 ---好水!!

    我以为我会是最坚强的那一个 我还是高估了自己 我以为你会是最无情的那一个 还是我贬低了自己 就算不能够在一起 我还是为你担心 就算你可能听不清 也代表我的心意 那北极星的眼泪 闪过你曾经的眼角迷离 那 ...

随机推荐

  1. js根据浏览器窗口大小实时改变网页文字大小

    目前,有了css3的rem,给我们的移动端开发带来了前所未有的改变,使得我们的开发更容易,更易兼容很多设备,但这个不在本文讨论的重点中,本文重点说说如何使用js来实时改变网页文字的大小. 代码: &l ...

  2. Android——KEYCODE列表

    电话键 键名 描述 键值   KEYCODE_CALL 拨号键 5 KEYCODE_ENDCALL 挂机键 6 KEYCODE_HOME 按键Home 3 KEYCODE_MENU 菜单键 82 KE ...

  3. LeetCode 231

    Power of Two Given an integer, write a function to determine if it is a power of two. /************* ...

  4. Css 应用一

    Placeholder使用 CSS3里有相应的通用的对Placeholder提示信息美化的方法.你可以设置提示信息文字的颜色,透明度,背景色等. 为了最大化的兼容所有浏览器,给CSS里的placeho ...

  5. poj1182(并查集)

    题目链接 分析:根据分析,关系的递推满足由[a,b]~[b,c]得:[a,c]=([a,b]+[b,c])%3;[a,d]=([a,b]+[b,c]+[c,d])%3.由rank数组表示关系 0 -  ...

  6. mybatis返回int类型报null

    解决这个问题,是当查出来为NULL时,结一个默认值,如:0. MySQL: SELECT IFNULL(MAX(id),0)AS sort FROM table Oracle: SELECT nvl( ...

  7. flume1&period;8 Interceptors拦截器(五)

    1. Flume Interceptors Flume有能力修改/删除流程中的events.这是在拦截器(interceptor)的帮助下完成的.拦截器(Interceptors)是实现org.apa ...

  8. Scanner和BufferReader的效率问题

    先给出一道题,测试平台是Acwing, 这道题是腾讯2019年春招提前批笔试第二题.题目不难,但是如果不注意细节,很容易TLE(超时) https://www.acwing.com/problem/c ...

  9. CorelDrawX8安装时提示已安装另一个版本

    (1)首先卸载VIsualC++ 2015 运行库. (2)如果有VisualC++ 2017运行库,卸载VisualC++2017运行库,即可.

  10. Android 安全退出应用程序的方法总结

    正常关闭应用程序: 当应用不再使用时,通常需要关闭应用,可以使用以下三种方法关闭android应用: 第一种方法:首先获取当前进程的id,然后杀死该进程. android.os.Process.kil ...