Cod sursa(job #1174846)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 24 aprilie 2014 00:01:42
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <iostream>
#include <fstream>
#include <utility>
#include <map>

using namespace std;

#define mod 1000000007
//int din[10005][10005];
map<pair<int,int>,bool> viz;
map<pair<int,int>,int> din;
int p_glob;

int cate(int n,int p)
{
    if(viz[make_pair(n,p)])
        return din[make_pair(n,p)];
    viz[make_pair(n,p)]=1;

    if(n==1)
    {
        din[make_pair(n,p)]=(p%mod);
        return din[make_pair(n,p)];
    }

    int i;
    for(i=1;i*i<p_glob;i++) //Astea sunt cazurile in care p/i da mult si aproape unic
        din[make_pair(n,p)]=(din[make_pair(n,p)]+cate(n-1,p/i))%mod;

    for(i=1;i*i<=p_glob;i++) //atentie la alea egale
    {
        int st=1;
        int dr=p_glob;
        int mijl=(p_glob+1)>>1;
        int r1=p+1;

        while(st<=dr)
        {
            if(p_glob/mijl<=i)
            {
                if(mijl<r1)
                    r1=mijl;
                dr=mijl-1;
            }
            else
                st=mijl+1;

            mijl=(st+dr)>>1;
        }

        st=1;
        dr=p_glob;
        mijl=(p_glob+1)>>1;
        int r2=0;

        while(st<=dr)
        {
            if(p/mijl>=i)
            {
                if(mijl>r2)
                    r2=mijl;
                st=mijl+1;
            }
            else
                dr=mijl-1;

            mijl=(st+dr)>>1;
        }

        if(r1<=r2)
            din[make_pair(n,p)]=(din[make_pair(n,p)]+1ll*(r2-r1+1)*(cate(n-1,i)))%mod;
    }

    return din[make_pair(n,p)];
}

int main()
{
    ofstream cout("date.out");

    int n,p,i,j,l,k;
    cin>>n>>p;

    for(l=1; l<=n; l++)
    {
        for(k=1; k<=p; k++)
        {
            /*for(i=1; i<=k; i++)
                din[1][i]=i%mod;

            for(i=2; i<=l; i++)
                for(j=1; j<=k; j++)
                    din[i][j]=(din[i][j-1]+din[i-1][k/j])%mod;
*/
            //cout<<din[l][k]-din[l][k-1]<<' ';

            p_glob=k;
            cout<<cate(l,k)<<' ';
        }

        cout<<'\n';
    }



    //cout<<cate(n,p)<<'\n';

    cout.close();
    return 0;
}