1.	DP over Divisors
/**
given x;
di=divisors of x;
n=di.size();
for(int i=1;i<=n;i++) ans[i]=rnd();
ans[i] should be=sum of ans[k] for all k such that di[i] is a divisor of k
Brute force DP= O((number of divisors of x)^2)
We can optimize it using prime factors of x.
Target complexity=O((number of divisors of x)*(unique prime factors of x))
*/
int32_t main()
{
     di=divisors of x
    d=di.size();
    for(int i=0; i<d; i++) id[di[i]]=i;
    for(int i=0;i<n;i++) ans[i]=rnd()%10;///initial answer for i-th divisor
    P=unique prime factors of x
    for(auto k:P)
    {
        for(int i=d-1; i>=0; i--)
        {
            if(di[i]%k==0)
            {
                ans[id[di[i]/k]]+=ans[i];
                //assert(id[di[i]/x.F]<i);
            }
        }
    }
    return 0;
}