题目: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
这个简单的谜题就是中国剩余定理的来历。
在艰难地弄懂了这个定理之后,小明開始设计一些复杂的同余方程组X mod ai = bi 来调戏别人,结果是必定的,都失败了。
但是在这个过程中,小明发现有时并不一定要把ai和bi告诉你。他仅仅须要告诉你,ai在区间 [1, X] 范围内每一个值取一次时,有K个ai使bi等于0,或有K个ai使bi不等于0,最小的X就能够求出来了。
你来试试看吧!
每组数据包括两个整数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
3
0 3
1 3
0 10
Case 1: 4
Case 2: 5
Case 3: 48
这道题学到了非常多东西。
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 数论 + 约数个数相关 腾讯编程马拉松复赛的更多相关文章
-
HDU(4528),BFS,2013腾讯编程马拉松初赛第五场(3月25日)
题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=4528 小明系列故事——捉迷藏 Time Limit: 500/200 MS (Java/O ...
-
2013腾讯编程马拉松初赛第〇场(HDU 4503) 湫湫系列故事——植树节
http://acm.hdu.edu.cn/showproblem.php?pid=4503 题目: 已知湫湫的班里共有n个孩子,每个孩子有Bi个朋友(i从1到n),且朋友关系是相互的,如果a小朋友和 ...
-
HDU 4508 沼泽湿地系列故事——记住减肥I (2013腾讯编程马拉松预赛第一)
pid=4508">http://acm.hdu.edu.cn/showproblem.php?pid=4508 题目大意: 给定一些数据. 每组数据以一个整数n開始,表示每天的食物清 ...
-
HDU 4508 湫湫系列故事——减肥记I (2013腾讯编程马拉松初赛第一场)
http://acm.hdu.edu.cn/showproblem.php?pid=4508 题目大意: 给定一些数据. 每组数据以一个整数n开始,表示每天的食物清单有n种食物. 接下来n行,每行两 ...
-
2013腾讯编程马拉松初赛第〇场(HDU 4504)威威猫系列故事——篮球梦
http://acm.hdu.edu.cn/showproblem.php?pid=4504 题目大意: 篮球赛假如我们现在已经知道当前比分 A:B,A代表我方的比分,B代表对方的比分,现在比赛还剩下 ...
-
2013腾讯编程马拉松||HDU 4505 小Q系列故事——电梯里的爱情 水水水
http://acm.hdu.edu.cn/showproblem.php?pid=4505 题目大意: 电梯最开始在0层,并且最后必须再回到0层才算一趟任务结束.假设在开始的时候已知电梯内的每个人要 ...
-
2013腾讯编程马拉松初赛第一场(3月21日) 湫湫系列故事——减肥记II ----线段树
题目:http://acm.hdu.edu.cn/showproblem.php?pid=4509 虽然制定了减肥食谱,但是湫湫显然克制不住吃货的本能,根本没有按照食谱行动! 于是,结果显而易见… 但 ...
-
2013腾讯编程马拉松初赛第〇场(3月20日)湫湫系列故事——植树节 HDOJ 4503
题目:http://acm.hdu.edu.cn/showproblem.php?pid=4503 思路:hint from a GOD-COW. 将每一个人模拟成图的一个点,两点连线当且仅当两人是朋 ...
-
2013腾讯编程马拉松初赛第二场(3月22日) 小Q系列故事——为什么时光不能倒流 ---好水!!
我以为我会是最坚强的那一个 我还是高估了自己 我以为你会是最无情的那一个 还是我贬低了自己 就算不能够在一起 我还是为你担心 就算你可能听不清 也代表我的心意 那北极星的眼泪 闪过你曾经的眼角迷离 那 ...
随机推荐
-
js根据浏览器窗口大小实时改变网页文字大小
目前,有了css3的rem,给我们的移动端开发带来了前所未有的改变,使得我们的开发更容易,更易兼容很多设备,但这个不在本文讨论的重点中,本文重点说说如何使用js来实时改变网页文字的大小. 代码: &l ...
-
Android——KEYCODE列表
电话键 键名 描述 键值 KEYCODE_CALL 拨号键 5 KEYCODE_ENDCALL 挂机键 6 KEYCODE_HOME 按键Home 3 KEYCODE_MENU 菜单键 82 KE ...
-
LeetCode 231
Power of Two Given an integer, write a function to determine if it is a power of two. /************* ...
-
Css 应用一
Placeholder使用 CSS3里有相应的通用的对Placeholder提示信息美化的方法.你可以设置提示信息文字的颜色,透明度,背景色等. 为了最大化的兼容所有浏览器,给CSS里的placeho ...
-
poj1182(并查集)
题目链接 分析:根据分析,关系的递推满足由[a,b]~[b,c]得:[a,c]=([a,b]+[b,c])%3;[a,d]=([a,b]+[b,c]+[c,d])%3.由rank数组表示关系 0 - ...
-
mybatis返回int类型报null
解决这个问题,是当查出来为NULL时,结一个默认值,如:0. MySQL: SELECT IFNULL(MAX(id),0)AS sort FROM table Oracle: SELECT nvl( ...
-
flume1.8 Interceptors拦截器(五)
1. Flume Interceptors Flume有能力修改/删除流程中的events.这是在拦截器(interceptor)的帮助下完成的.拦截器(Interceptors)是实现org.apa ...
-
Scanner和BufferReader的效率问题
先给出一道题,测试平台是Acwing, 这道题是腾讯2019年春招提前批笔试第二题.题目不难,但是如果不注意细节,很容易TLE(超时) https://www.acwing.com/problem/c ...
-
CorelDrawX8安装时提示已安装另一个版本
(1)首先卸载VIsualC++ 2015 运行库. (2)如果有VisualC++ 2017运行库,卸载VisualC++2017运行库,即可.
-
Android 安全退出应用程序的方法总结
正常关闭应用程序: 当应用不再使用时,通常需要关闭应用,可以使用以下三种方法关闭android应用: 第一种方法:首先获取当前进程的id,然后杀死该进程. android.os.Process.kil ...