1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
| #define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> #include <unordered_map> using namespace std;
#define Mid ((l+r)/2) #define pb push_back #define mp make_pair #define ls ((rt)<<1) #define rs ((rt)<<1|1) #define sq(u) ((u)*(u)) #define Abs(u) ((u)>0?(u):-(u)) #define ze(u) (Abs(u)<eps) #define eq(u, v) (ze((u)-(v))) #define Sgn(u) ((u)>eps?1:((u)<-eps?-1:0)) typedef long long LL; typedef unsigned long long UL; typedef double DB; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const DB eps = 1e-8; const DB pi = acos(-1.0);
const int N = (int)1e5; const int M = (int)4e3; const int mxn = N + 5; const int mxm = M + 5;
LL ans = 1e18 + 7;
LL SUM(LL a, LL b) { LL cnt = 0; for (a /= b; a; a /= b) cnt += a; return cnt; }
LL sum = 0, upperlim = 1;
void test(LL row, LL ld, LL rd) { if (row != upperlim) { LL pos = upperlim & ~(row | ld | rd); while (pos) { long p = pos & -pos; pos -= p; test(row + p, (ld + p) << 1, (rd + p) >> 1); } } else sum++; }
LL f[84] = { 0,1,1,2 };
void fib() { for (int i = 3; i <= 83; i++) { f[i] = f[i - 1] + f[i - 2]; } }
int main() { fib();
LL x, m; scanf("%lld %lld", &x, &m);
LL v = 1, flag = 0; for (v = 1; v <= 83; v++) { if (x == f[v]) { flag = 1; break; } }
if (flag) { for (LL i = 2; i * i <= m; ++i) { LL cnt = 0; while (m % i == 0)++cnt, m /= i; if (cnt)ans = min(ans, SUM(x, i) / cnt); } if (m > 1)ans = min(ans, SUM(x, m)); printf("%lld\n", ans); return 0; }
int n = x % min(13LL, m) + 1LL;
upperlim = (upperlim << n) - 1;
test(0, 0, 0); printf("%lld\n", sum);
return 0; }
|