27E - Number With The Given Amount Of Divisors - CodeForces Solution

brute force dp number theory *2000

Please click on ads to support us..

Python Code: 

n=int(input())
primes=[2,3,5,7,11,13,17,19,23,29]
def f(n,i):
    if n==1:
    return 1
  if i==10:
    return 10**18
  ans=10**18
  for j in range(2,n+1):
    if n%j==0:
      ans=min(ans,primes[i]**(j-1)*f(n//j,i+1))
  return ans
print(f(n,0))

C++ Code: 

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 2e3 + 5;
const long long INF = 1e18 + 1; 
int n,m,q,timer,k;
long long dp[N + 1][N + 1];
long long a[N + 1][N + 1];
int pw[N + 1];
int p[9] = {2,3,5,7,11,13,17,19,23};
long long f(int n,int k){
      if(n == 1) return 1; 
      if(k < 0) return INF; 
      if(dp[n][k]) return dp[n][k]; 
      long long ans = f(n,k - 1);
      for(int i = 0; i <= pw[p[k]]; i++){
           if(n % (i + 1) == 0){
             long long to = f(n / (i + 1) , k - 1);
             if(to < INF / a[p[k]][i]){
                    ans = min(ans, (1ll) * to * a[p[k]][i]); 
                }
           }
      }
      return dp[n][k] = ans; 
}
int main(){
      scanf("%d",&n);
      for(int i = 0; i < 9; i++){
           a[p[i]][0] = 1; 
           while((long long) a[p[i]][pw[p[i]]] < INF / p[i]){
              pw[p[i]]++;
              a[p[i]][pw[p[i]]] = (1ll) * a[p[i]][pw[p[i]] - 1] * p[i]; 
           }
      }
      long long ans = f(n,8);
      printf("%lld \n",ans);
}


Comments

Submit
0 Comments
More Questions

1516A - Tit for Tat
622. Design Circular Queue
814. Binary Tree Pruning
791. Custom Sort String
787. Cheapest Flights Within K Stops
779. K-th Symbol in Grammar
701. Insert into a Binary Search Tree
429. N-ary Tree Level Order Traversal
739. Daily Temperatures
647. Palindromic Substrings
583. Delete Operation for Two Strings
518. Coin Change 2
516. Longest Palindromic Subsequence
468. Validate IP Address
450. Delete Node in a BST
445. Add Two Numbers II
442. Find All Duplicates in an Array
437. Path Sum III
436. Find Right Interval
435. Non-overlapping Intervals
406. Queue Reconstruction by Height
380. Insert Delete GetRandom O(1)
332. Reconstruct Itinerary
368. Largest Divisible Subset
377. Combination Sum IV
322. Coin Change
307. Range Sum Query - Mutable
287. Find the Duplicate Number
279. Perfect Squares
275. H-Index II