Advertisement
Guest User

Untitled

a guest
Mar 10th, 2019
381
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.12 KB | None | 0 0
  1. #ifdef DEBUG
  2. #define _GLIBCXX_DEBUG
  3. #endif
  4.  
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. typedef long double ld;
  10.  
  11. #ifdef DEBUG
  12. #define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
  13. #else
  14. #define eprintf(...) ;
  15. #endif
  16.  
  17. #define sz(x) ((int) (x).size())
  18. #define TASK "text"
  19.  
  20. const int inf = (int) 1.01e9;
  21. const long long infll = (long long) 1.01e18;
  22. const ld eps = 1e-9;
  23. const ld pi = acos((ld) -1);
  24.  
  25. #ifdef DEBUG
  26. mt19937 mrand(300);
  27. #else
  28. mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
  29. #endif
  30.  
  31. int rnd(int x) {
  32.   return mrand() % x;
  33. }
  34.  
  35. const int mod = (int) 1e9 + 7;
  36.  
  37. int mul(int a, int b) {
  38.   return (long long) a * b % mod;
  39. }
  40.  
  41. void add(int &a, int b) {
  42.   a += b;
  43.   if (a >= mod) {
  44.     a -= mod;
  45.   }
  46. }
  47.  
  48. int gcd(int a, int b) {
  49.   return (b ? gcd(b, a % b) : a);
  50. }
  51.  
  52. const int maxn = (int) 1e7 + 5;
  53. int lDiv[maxn], phi[maxn];
  54. vector<int> pr;
  55. int f[maxn], inv[maxn], finv[maxn];
  56.  
  57. void precalc() {
  58.   for (int i = 2; i < maxn; i++) {
  59.     if (!lDiv[i]) {
  60.       lDiv[i] = i;
  61.       pr.push_back(i);
  62.     }
  63.     for (int j = 0; j < sz(pr) && pr[j] <= lDiv[i]; j++) {
  64.       int p = pr[j] * i;
  65.       if (p >= maxn) {
  66.         break;
  67.       }
  68.       lDiv[p] = pr[j];
  69.     }
  70.   }
  71.   phi[1] = 1;
  72.   for (int i = 2; i < maxn; i++) {
  73.     int p = lDiv[i];
  74.     int j = i / p;
  75.     if (lDiv[j] != p) {
  76.       phi[i] = phi[j] * (p - 1);
  77.     } else {
  78.       phi[i] = phi[j] * p;
  79.     }
  80.   }
  81.   f[0] = 1;
  82.   for (int i = 1; i < maxn; i++) {
  83.     f[i] = mul(f[i - 1], i);
  84.   }
  85.   inv[1] = 1;
  86.   for (int i = 2; i < maxn; i++) {
  87.     inv[i] = (mod - (long long) (mod / i) * inv[mod % i] % mod) % mod;
  88.   }
  89.   finv[0] = 1;
  90.   for (int i = 1; i < maxn; i++) {
  91.     finv[i] = mul(finv[i - 1], inv[i]);
  92.   }
  93. }
  94.  
  95. int c(int n, int k) {
  96.   if (k < 0 || n < k) {
  97.     return 0;
  98.   }
  99.   return mul(f[n], mul(finv[k], finv[n - k]));
  100. }
  101.  
  102. int n, m;
  103.  
  104. bool read() {
  105.   if (scanf("%d%d", &m, &n) < 2) {
  106.     return false;
  107.   }
  108.   return true;
  109. }
  110.  
  111. int get(int d) {
  112.   return mul(c(m / d - 1, n / d - 1), phi[d]);
  113. }
  114.  
  115. void solve() {
  116.   int res = 0;
  117.   int g = gcd(n, m);
  118.   for (int d = 1; d * d <= g; d++) {
  119.     if (!(g % d)) {
  120.       add(res, get(d));
  121.       if (d * d != g) {
  122.         add(res, get(g / d));
  123.       }
  124.     }
  125.   }
  126.   if (n & 1) {
  127.     if (m & 1) {
  128.       add(res, mul(c((m - 1) / 2, (n + 1) / 2 - 1), n));
  129.     } else {
  130.       add(res, mul(c(m / 2 - 1, (n + 1) / 2 - 1), n));
  131.     }
  132.   } else {
  133.     if (!(m & 1)) {
  134.       add(res, mul(c(m / 2 - 1, n / 2 - 1), n / 2));
  135.     }
  136.     for (int t0 = 0; t0 < 2; t0++) {
  137.       for (int t1 = 0; t1 < 2; t1++) {
  138.         int x = m;
  139.         int nonzero = (n - 2) / 2;
  140.         if (t0) {
  141.           x--;
  142.         } else {
  143.           nonzero++;
  144.         }
  145.         if (t1) {
  146.           x--;
  147.         } else {
  148.           nonzero++;
  149.         }
  150.         if (x & 1) {
  151.           continue;
  152.         }
  153.         int y = (n - 2) / 2 + 2;
  154.         add(res, mul(c(x / 2 - nonzero + y - 1, y - 1), n / 2));
  155.       }
  156.     }
  157.   }
  158.   res = mul(res, mul(inv[n], inv[2]));
  159.   {
  160.     int l = (m + 1) / 2;
  161.     int bad = c(m - l, n - 1);
  162.     if (n & 1) {
  163.       int x = m - l;
  164.       if (x & 1) {
  165.         add(bad, c((x - 1) / 2, (n + 1) / 2 - 1));
  166.       } else {
  167.         add(bad, c(x / 2, (n + 1) / 2 - 1));
  168.       }
  169.     } else {
  170.       for (int t0 = 0; t0 < 2; t0++) {
  171.         for (int t1 = 0; t1 < 2; t1++) {
  172.           int x = m - l;
  173.           int nonzero = (n - 2) / 2;
  174.           if (t0) {
  175.             x--;
  176.           }
  177.           if (t1) {
  178.             x--;
  179.           } else {
  180.             nonzero++;
  181.           }
  182.           if (x & 1) {
  183.             continue;
  184.           }
  185.           int y = (n - 2) / 2 + 2;
  186.           add(bad, c(x / 2 - nonzero + y - 1, y - 1));
  187.         }
  188.       }
  189.     }
  190.     bad = mul(bad, inv[2]);
  191.     add(res, mod - bad);
  192.   }
  193.   printf("%d\n", res);
  194. }
  195.  
  196. int main() {
  197.   precalc();
  198. #ifdef DEBUG
  199.   assert(freopen(TASK ".in", "r", stdin));
  200.   assert(freopen(TASK ".out", "w", stdout));
  201. #endif
  202.   int t;
  203.   scanf("%d", &t);
  204.   while (read()) {
  205.     solve();
  206. #ifdef DEBUG
  207.     eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
  208. #endif
  209.   }
  210.   return 0;
  211. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement