小明系列故事——未知剩餘系（反素數，好）

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

Time Limit: 500/200 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 1281    Accepted Submission(s): 319

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

30 3

1 3

0 10

Sample Output

Case 1: 4Case 2: 5

Case 3: 48

Source

​​2013騰訊程式設計馬拉松複賽第三場（3月31日）​​

題解：當type是0的時候是反素數模版，不過要剪枝，否則逾時；當type是1

的時候是因子個數是x-k個；用倆重循環；

代碼：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const double PI=acos(-1.0);
#define SI(x) scanf("%d",&x)
#define SL(x) scanf("%lld",&x)
#define PI(x) printf("%d",x)
#define PL(x) printf("%lld",x)
#define T_T while(T--)
#define P_ printf(" ")
int prim[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
typedef unsigned long long uLL;
const int MAXN=60010;
const uLL INF=(uLL)~0;
uLL ans;
int k;
int dp[MAXN];
void initial(){
  for(int i=0;i<MAXN;i++)dp[i]=i;
  for(int i=1;i<MAXN;i++){
    for(int j=i;j<MAXN;j+=i)dp[j]--;
    if(dp[dp[i]]==0)//如果沒被使用就讓dp[dp[i]]=i； **
    dp[dp[i]]=i;
    dp[i]=0;//目前值已經沒用了，就為0 **
  }
}
void dfs(int pos,uLL v,int num){
  if(num==k&&ans>v)ans=v;
  for(int i=1;i<=62;i++){
    if(num*(i+1)>k||ans/prim[pos]<v)break;//剪枝； 
    v*=prim[pos];
    if(k%(num*(i+1))==0)dfs(pos+1,v,num*(i+1));//剪枝 
  }
}
int main(){
  int T,kase=0;
  SI(T);
  initial();
  T_T{
    int type;
    SI(type);SI(k);
    ans=INF;
    if(type)ans=dp[k];
    else{
      dfs(0,1,1);
    }
    printf("Case %d: ",++kase);
    if(ans==0)puts("Illegal");
    else if(ans==INF)puts("INF");
    else printf("%llu\n",ans);
  }
  return 0;
}