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;
}