#include #include #include #include #include #include #include #include #include #include #include #include #include #pragma warning(disable:4996) typedef long long ll; #define MIN(a, b) ((a)>(b)? (b): (a)) #define MAX(a, b) ((a)<(b)? (b): (a)) #define LINF 9223300000000000000 #define INF 2140000000 const long long MOD = 1000000007; using namespace std; ll gcd(ll a, ll b) { if(b == 0) return a; return gcd(b,a%b); } ll lcm(ll a, ll b) { ll g = gcd(a,b); return a / g * b; // Be careful not to overflow } vector pp; void preparePrime( int maxp ) { int i; vector a(maxp+1); for(i=2; i<=maxp; i++) { int k=i+i; while(k<=maxp) { a[k]=1; k+=i; } } for(i=2; i<=maxp; i++) { if(a[i]==0) pp.push_back( i ); } return; } void decompositPrime( ll a, vector >& vv ) { preparePrime( (int)sqrt((double)a)+1 ); int i; for(i=0; i<(int)pp.size(); i++) { int count = 0; while(a % pp[i] == 0 ) { a /= pp[i]; count ++; } if(count>0) vv.push_back( make_pair( pp[i], count ) ); if (a==1) break; } if(a>1) { vv.push_back( make_pair( a, 1 ) ); } return; } int n,k,m; vector > vv; int ans; void dfs( int i, ll curr ) { if(i==vv.size()) { if(curr<=m) { #ifdef _DEBUG printf("%d ", curr); #endif ans++; } return; } int p; ll tmp=curr; for(p=0; p<=vv[i].second*k; p++) { dfs( i+1, tmp ); tmp*=vv[i].first; if(tmp>m) break; } return; } int main(int argc, char* argv[]) { scanf("%d%d%d", &n,&k,&m); decompositPrime( n, vv); ans=0; dfs( 0, 1 ); #ifdef _DEBUG printf("\n"); #endif printf("%d\n", ans); return 0; }