Cod sursa(job #2557965)

Utilizator suntbossgiani kirita suntboss Data 26 februarie 2020 10:22:35
Problema Descompuneri Scor 8
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <vector>
#include <fstream>
#include <iostream>
#include <cmath>
#include <map>
#include <algorithm>
#define ll  long long int

#include <bits/stdc++.h>
using namespace std;
ifstream f("desc.in");
ofstream g("desc.out");
ll n,k;
vector <ll> divizori;
vector <pair<int,int> > v[5000];
ll  mat[1005][1005];
void calcdiv(int i)
{
   int val=divizori[i];
   int l=0,r=divizori.size()-1;

   while(l<r)
   {
       while(r>=0&&divizori[r]*divizori[l]>val)
       {
           r--;
       }
       if(r<0) break;
       if(l>r) break;
       if(divizori[r]*divizori[l]==val)
       {
           v[i].push_back({l,r});
       }
       l++;
   }
   v[i].push_back({i,0});
}
ll  calcperm(int lastdiv,int currdiv)
{
    if(currdiv==0) return 1;
    if(divizori[lastdiv]>divizori[currdiv]) return 0;
    if(mat[lastdiv][currdiv]!=-1) return mat[lastdiv][currdiv];

    mat[lastdiv][currdiv]=0;
    int st=0,dr=v[currdiv].size()-1;
    //int rasp=dr;
/*
    while(st<dr)
    {
        int mij=(st+dr)/2;
        if(v[currdiv][mij].first>=lastdiv)
        {
            dr=mij-1;
            rasp=mij;
        }
        else st=mij+1;

    }
    */
    int rasp=lower_bound(v[currdiv].begin(),v[currdiv].end(),make_pair(lastdiv,-1))-v[currdiv].begin();
    rasp=max(rasp,1);
    for(int i=rasp;i<v[currdiv].size();i++)
    {
        if(divizori[v[currdiv][i].first]<divizori[lastdiv]) continue;
        else
        {
            mat[lastdiv][currdiv]+=calcperm(v[currdiv][i].first,v[currdiv][i].second);
        }
    }
    return mat[lastdiv][currdiv];



}
int main()
{
f>>n>>k;
for(int i=1;i*i<=n;i++)
{
    if(n%i==0)
    {
        if(n/i!=i)
        {
            divizori.push_back(i);
            divizori.push_back(n/i);
        }
        else divizori.push_back(i);
    }
}
sort(divizori.begin(),divizori.end());
memset(mat,-1,sizeof mat);
for(int i=1;i<divizori.size();i++)
{
    calcdiv(i);


}
g<<calcperm(0,divizori.size()-1);
}