hdu 4542 小明系列故事——未知剩余系 数论

本文主要是介绍hdu 4542 小明系列故事——未知剩余系 数论，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=4542

type = 0

对于整数m = p1^a1*p2^a2....pi^ai （pi为质数），其约数个数 n = (a1+1)*(a2+1)....*(ai+1)
所以对n进行分解，找到m的最小值即可。
做法是预处理出所有 m 对应的最小 n。
type = 1

也是暴力预处理打表，看代码好理解

#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<string>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
void fre(){freopen("t.txt","r",stdin);}
#define ls o<<1
#define rs o<<1|1
#define MS(x,y) memset(x,y,sizeof(x))
#define debug(x) printf("%d",x);
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
const int MAXN = 1<<30;
const int N = 50000;
const LL LINF = (LL)1<<62;
const double DINF = pow(2.0,62);int p[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};  //素数LL dp[18][N];//dp[i][j] 表示用p[0]~p[i]，相乘得到的“有j个约数”的最小数。
int num1[N<<1],num2[N<<1];
int main()
{//fre();int T,i,j,k,cas = 0,r,type,n;LL tem;MS(dp,-1);tem = 1;for(i = 0; i < 63; ++i){dp[0][i+1] = tem;if(double(tem)*double(p[0]) > DINF) break;tem*=2;}for(i = 0; i < 15; ++i)for(j = 1; j < N; ++j){if(dp[i][j]==-1) continue;tem = p[i+1];for(k = 1; k < 63; ++k){if( double(dp[i][j])*double(tem) > DINF) break;r = j*(k+1); if(r>=N) break;if(dp[i+1][r] == -1 || dp[i+1][r] > dp[i][j]*tem) dp[i+1][r] = dp[i][j]*tem;if(double(tem)*double(p[i+1]) > DINF) break;tem*=p[i+1];}}for(i = 0; i < 2*N; ++i) num1[i] = i-1,num2[i] = -1;//num1[i]表示i的非约数个数（数的范围是1～i-1），num2[i]表示“有i个约数”的最小数。for(i = 1; i < 2*N; ++i){if(num2[num1[i]]==-1) num2[num1[i]] = i;for(j = i+i; j < 2*N; j+=i) num1[j]--;}scanf("%d",&T);while(T--){printf("Case %d: ",++cas);scanf("%d%d",&type,&n);if(type){if(num2[n] == -1) printf("Illegal\n");else printf("%d\n",num2[n]);}else{LL ans = -1;for(i = 0; i < 16; ++i){if(dp[i][n] == -1) continue;if(ans == -1 || dp[i][n] < ans) ans = dp[i][n];}if(ans == -1 || ans > LINF) printf("INF\n");else printf("%I64d\n",ans);}}
}

这篇关于hdu 4542 小明系列故事——未知剩余系 数论的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---