HDU 4542:小明系列故事——未知剩余系

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

Time Limit : 500/200ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 4 Accepted Submission(s) : 2

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”。 [b][Technical Specification][/b] 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

2013腾讯编程马拉松复赛第三场(3月31日)

题目真的能把人绕晕
第一眼真的看不懂什么操作,十分钟后还是看不懂什么操作
这种条件太弱了吧
搜了大佬的题解
这种转化太聪明了
type=1 求因子的个数为k的最小整数X,如果这个数大于2^62次方,输出INF,否则输出答案
type=0 求因子的个数为n-k的最小整数x。
结果要用到反素数。
反素数的定义:对于任何正整数n,其约数个数记为f(n),例如f(6)=4,如果某个正整数n满足:对任意的正整数i(0<i<n),都有f(i)<f(n),那么称n为反素数。
则这个题目就是让求一个因子数等于n的最小数字。根据反素数的定义可知这个数字一定是反素数。

反素数板子
https://blog.csdn.net/wyxeainn/article/details/75333091
这篇博客找到的

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
long long ans;
int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,47,53};
 
void dfs(int pos,int value,int num) {
	if (num>n||pos>15) return;//如果当前值的因子个数比n大或者当前位置超过素数表,则返回 
	if (num==n)    //如果到达,看看是否有必要更新n 
	   if (value<ans)
	      {
	      	ans=value;return;    
		  }
       for (int i=1;i<63;i++) {//这里value乘上pos位置上的素数超过ans,不用考虑,因为我们要的是最小的ans,value>ans/prime[pos] 
       	if (value>ans/prime[pos]||num*(i+1)>n)
       	  break;
       	value=value*prime[pos];
       	if (n%(num*(i+1))==0)//(i+1是n的因数 
       	   {
       	   	   dfs(pos+1,value,num*(i+1));
			}
	   }
	
}

int main()
{
   while (~scanf("%d",&n))
   {
      ans=1e19;
	  dfs(0,1,1);
	  cout<<ans<<endl; 
   }
   return 0;

//凑出的算法崩掉了,明日再调

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
long long ans;
#define maxn 50010
int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,47,53};
long long a[maxn];
long long res[maxn];
const long long INF=4611686018427387901;
void init(){   
    for (int i=1;i<maxn;i++)
        a[i]=i;
    for (int i=1;i<maxn;i++)
    {
        for (int j=i;j<maxn;j+=i)
          a[j]--;
    }
    for (int i=1;i<maxn;i++) 
       if (!res[a[i]])
         res[a[i]]=i;
} 
void dfs(int pos,unsigned long long value,int num) {
    if (num>n||pos>15) return;//如果当前值的因子个数比n大或者当前位置超过素数表,则返回 
    if (num==n)    //如果到达,看看是否有必要更新n 
       if (value<ans)
          {
              ans=value;//printf("ans函数内=%lld",ans);return;    
          }
       for (int i=1;i<63;i++) {//这里value乘上pos位置上的素数超过ans,不用考虑,因为我们要的是最小的ans,value>ans/prime[pos] 
           if (value>ans/prime[pos]||num*(i+1)>n)
             break;
           value=value*prime[pos];
           if (n%(num*(i+1))==0)//(i+1是n的因数 
              {
                     dfs(pos+1,value,num*(i+1));
            }
       }
   
}
int main()
{
   init();
   int t;
   int cnt=0; 
   scanf("%d",&t);
   int type;
   while (t--)
   {
        
        scanf("%d%d",&type,&n);
      ans=1e19;
    // printf("ans==%lld",ans);
     long long num=INF;
     dfs(0,1,1);
     if (type==1) num=res[n];
      else {
      num=ans;
     // printf("type=%d,ans=%lld\n",type,ans);
        }
     printf("Case %d: ",++cnt);
     if (num>INF)
       printf("INF\n");
    else if (num==0)
     printf("Illegal\n");
    else printf("%lld\n",num);     
   }
   return 0;
}
全部评论

相关推荐

深夜书店vv:腾讯是这样的,去年很多走廊都加桌子当工区
点赞 评论 收藏
分享
避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务