#DFS# [校测 年会小游戏][luogu P1463] [POI2002][HAOI2007]反素数

Title

P1463 [POI2002][HAOI2007]反素数

Solution

注意两数相乘大于另一个数的判断中可能会出现爆long long的情况，所以尽量换成除法

对于这一道题目

1. 最多会出现的质因数不超过10个
   2.$x$的质因子是连续的若干个最小的质数，并且指数单调递减 。

Code

#include<cstdio>
#include<algorithm>
#define ll long long 
#define rep(i,x,y) for(ll i=x;i<=y;i++)
using namespace std; 
const ll prime[17]={
    0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53}; 
ll T,n,m,cnt,cntt; 
void dfs(ll dep,ll x,ll y,ll last){
    if (dep>15||y>n) return; if (x>cnt||((x==cnt)&&(y<cntt))) {
    cnt=x; cntt=y;}rep(i,1,last)if (n/prime[dep]>=y)dfs(dep+1,x*(i+1),y*=prime[dep],i); 
}
int main(){
    scanf("%lld",&T); while(T--){
    scanf("%lld",&n); cntt=1e18; cnt=-1e18; dfs(1,1,1,63); printf("%lld %lld\n",cntt,cnt); }
}