Entrenamiento IOI - Etapa #2 - Problem: Digit Product - Judge: omegaUp - 30/11/2014 - Puntaje: 100% (AC) - Factorization + DP (Theory mathematical + Programming Dynamic).

gistfile1.cpp

#include <bits/stdc++.h>
#define optimize ios_base::sync_with_stdio(0);cin.tie(0)
#define sz size
using namespace std;
typedef long long int lli;
lli A, N;
string cad;
int digits[4005];
lli izq[40005];
lli der[40005];
int p = 0;
lli dp[40005]={0};
lli ans = 0;
void factorize() {
    lli i;
    for(i=1; i*i<=A; ++i) {
        if( (A%i)==0 ) {
            izq[p] = i;
            der[p++] = (A/i);
        }
    }
}
void subsets(){
    int i,j;
    lli sum = 0;
    for(i=0; i<N; ++i) {
        sum = 0;
        for(j=i; j<N; ++j) {
            sum += digits[j];
            ++dp[sum];
        }
    }
}
int main() {
    optimize;
    int i,j,k;
    cin>>A;
    cin>>cad;
    N=cad.sz();
    for(i=0; i<N; ++i) {
        digits[i] = cad[i]-'0';
    }
    factorize();
    subsets();
    lli tmp = 0;
    for(i=0; i<p-1; ++i) {
        tmp = 2*( dp[izq[i]] * dp[der[i]] );
        ans += tmp;
    }
    tmp = 2 * dp[izq[p-1]] * dp[der[p-1]];
    if( izq[p-1] == der[p-1] ){
        tmp /= 2;
    }
    ans += tmp;
    cout<<ans<<"\n";
    return 0;
}