Pagini recente » Cod sursa (job #430468) | Istoria paginii runda/111111111/clasament | Cod sursa (job #2854764) | Cod sursa (job #502893) | Cod sursa (job #1174846)
#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;
}