小明系列故事——未知剩余系
Time Limit: 500/200 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Problem Description
“今有物不知其数,三三数之有二,五五数之有三,七七数之有二,问物几何?”
这个简单的谜题就是中国剩余定理的来历。
在艰难地弄懂了这个定理之后,小明开始设计一些复杂的同余方程组X mod ai = bi 来调戏别人,结果是必然的,都失败了。
可是在这个过程中,小明发现有时并不一定要把ai和bi告诉你。他只需要告诉你,ai在区间 [1, X] 范围内每个值取一次时,有K个ai使bi等于0,或有K个ai使bi不等于0,最小的X就可以求出来了。
你来试试看吧!
这个简单的谜题就是中国剩余定理的来历。
在艰难地弄懂了这个定理之后,小明开始设计一些复杂的同余方程组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
每组数据包含两个整数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
思路:0:反素数深搜;1:打表;详见代码;
反素数的剪枝很重要;
#include<bits/stdc++.h> using namespace std; #define ll long long #define esp 0.00000000001 #define pi 4*atan(1) const int N=1e5+10,M=2e7+10,inf=1e9+10,mod=1e9+9; const ll INF=4611686018427387901; int p[N]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,53,59}; ll K,num; ll a[N]; ll ans[N]; void init() { for(int i=1;i<N;i++) a[i]=i; for(int i=1;i<N;i++) { for(int t=i;t<N;t+=i) a[t]--; } for(int i=1;i<N;i++) if(!ans[a[i]]) ans[a[i]]=i; } void dfs(int pos,ll ans,ll sum,ll pre) { if(sum>K)return; if(sum==K) num=min(ans,num); for(ll i=1;i<=pre;i++) { if(INF/ans<p[pos])break; ans*=p[pos]; if(K%(sum*(i+1))==0) dfs(pos+1,ans,sum*(i+1),i); } } int main() { init(); int T,cas=1; scanf("%d",&T); while(T--) { int flag; scanf("%d%lld",&flag,&K); num=INF; if(flag==1) num=ans[K]; else dfs(0,1,1,63); printf("Case %d: ",cas++); if(num>=INF) printf("INF "); else if(num==0) printf("Illegal "); else printf("%lld ",num); } return 0; }