[Solved] Sum a number with divisors to get another number

by


You can solve this using dynamic programming 

#include <iostream>
using namespace std;
#define INF 1000000007
int main() {
    // your code goes here
    int dp[101] = {0};
    int a,b,i,j;
    scanf("%d%d",&a, &b);
    for(i=a;i<=b;i++)
        dp[i] = INF;
    dp[a] = 0;
    for(i=a; i<=b; i++){
        for(j=2; j*j<=i; j++){
            if(i%j == 0){
                dp[i+j] = min(dp[i+j], dp[i]+1);
                dp[i+i/j] = min(dp[i+i/j], dp[i]+1);
            }
        }
    }
    printf("%d\n", dp[b]);
    return 0;
}

dp[i] would update all the i+j where j is a factor of i

Complexity O(n*sqrt(n))

check it out in the online compiler

2

solved Sum a number with divisors to get another number