51nod 1060 最复杂的数（数论，反素数）

题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1060

题解：可以去学习一下反素数。

#include <iostream>

#include <cstring>

#define inf 1000000000000000007

using namespace std;

typedef unsigned long long ull;

const int M = 1e6 + 10;

ull n , dp[M];

int prime[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};

void dfs(int deep , ull sum , int num) {

    dp[num] = min(dp[num] , sum);

    for(int i = 1 ; i <= 63 ; i++) {

        if(sum > 1e18 / prime[deep]) break;

        dfs(deep + 1 , sum * prime[deep] , num * (i + 1));

        sum *= prime[deep];

    }

}

int main() {

    int t;

    scanf("%d" , &t);

    for(int i = 0 ; i < M ; i++) dp[i] = -inf;

    dfs(0 , 1 , 1);

    while(t--) {

        scanf("%lld" , &n);

        int ans;

        for(int i = M - 1 ; i >= 1 ; i--) {

            if(dp[i] <= n && dp[i] != 0) {ans = i;  break;}

        }

        printf("%lld %d\n" , dp[ans] , ans);

    }

    return 0;

}

巴特西

51nod 1060 最复杂的数（数论，反素数）

最新文章

热门文章