SHARE
TWEET

Untitled

a guest Oct 18th, 2019 95 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <vector>
  2. #include <stdio.h>
  3. #include <iostream>
  4. #include <cmath>
  5. #include <cassert>
  6. // #include <bits/stdc++.h>
  7.  
  8. #define hash ajlasd
  9.  
  10. using namespace std;
  11.  
  12. typedef long long ll;
  13.  
  14. template<class T>
  15. void print(vector<T> s){
  16.     for (T i : s)
  17.         cout << i << " ";
  18.     cout << endl;
  19. }
  20.  
  21. namespace fft{
  22.  
  23.     typedef double dbl;
  24.     typedef long long ll;
  25.  
  26.     struct Complex{
  27.         dbl x, y;
  28.         Complex(dbl x = 0, dbl y = 0) : x(x), y(y) {}
  29.     };
  30.  
  31.     Complex operator + (Complex a, Complex b) { return Complex(a.x + b.x, a.y + b.y); }
  32.     Complex operator - (Complex a, Complex b) { return Complex(a.x - b.x, a.y - b.y); }
  33.     Complex operator * (Complex a, Complex b) { return Complex(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); }
  34.     Complex conj(Complex a) { return Complex(a.x, -a.y); }
  35.  
  36.     int base = 1;
  37.     const dbl PI = atan2(0, -1);
  38.     vector<Complex> roots = {{0, 0}, {1, 0}};
  39.     vector<int> rev = {0, 1};
  40.  
  41.     void ensureBase(int b){
  42.         if (b <= base)
  43.             return;
  44.  
  45.         rev.resize(1 << b);
  46.         for (int i = 0; i < (1 << b); i++)
  47.             rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (b - 1));
  48.  
  49.         roots.resize(1 << b);
  50.         while (base < b){
  51.             dbl angle = PI / (1 << base);
  52.             for (int i = (1 << (base - 1)); i < (1 << base); i++){
  53.                 roots[i << 1] = roots[i];
  54.                 dbl angle_i = (2 * i + 1 - (1 << base)) * angle;
  55.                 roots[(i << 1) + 1] = Complex(cos(angle_i), sin(angle_i));
  56.             }
  57.             base++;
  58.         }
  59.     }
  60.  
  61.     void fft(vector<Complex> &f, int n){
  62.         int shift = 0;
  63.         while ((1 << shift) < n)
  64.             shift++;
  65.         ensureBase(shift);
  66.         shift = base - shift;
  67.         for (int i = 0; i < n; i++)
  68.             if (i > (rev[i] >> shift))
  69.                 swap(f[i], f[rev[i] >> shift]);
  70.  
  71.         for (int len = 1; len < n; len *= 2){
  72.             for (int i = 0; i < n; i += 2 * len){
  73.                 for (int j = i, k = i + len; j < i + len; j++, k++){
  74.                     Complex z = f[k] * roots[k - i];
  75.                     f[k] = f[j] - z;
  76.                     f[j] = f[j] + z;
  77.                 }
  78.             }
  79.         }
  80.     }
  81.  
  82.     vector<Complex> f;
  83.     vector<ll> answer;
  84.  
  85.     vector<ll> multiply(vector<int> &a, vector<int> &b){
  86.         int need = a.size() + b.size() - 1;
  87.         int bb = 0;
  88.         while ((1 << bb) < need)
  89.             bb++;
  90.         ensureBase(bb);
  91.         int n = (1 << bb);
  92.         f.resize(n);
  93.         for (int i = 0; i < n; i++){
  94.             f[i].x = (i < a.size() ? a[i] : 0);
  95.             f[i].y = (i < b.size() ? b[i] : 0);
  96.         }
  97.         fft(f, n);
  98.         Complex r = Complex(0, -0.25 / n);
  99.         for (int i = 0; i <= n / 2; i++){
  100.             int j = (n - i) & (n - 1);
  101.             Complex z = (f[j] * f[j] - conj(f[i] * f[i])) * r;
  102.             if (i != j)
  103.                 f[j] = (f[i] * f[i] - conj(f[j] * f[j])) * r;
  104.             f[i] = z;
  105.         }
  106.         fft(f, n);
  107.         answer.resize(need);
  108.         for (int i = 0; i < need; i++)
  109.             answer[i] = (ll)(f[i].x + 0.5);
  110.         // print(answer);
  111.         return answer;
  112.     }
  113.  
  114.     // const int k = 15;
  115.  
  116.     // vector<int> multiplyWithMod(vector<int> &a, vector<int> &b, int mod){
  117.     //  int kk = (1 << k);
  118.     //  int kkk = (kk << k) % mod;
  119.     //  int need = a.size() + b.size() - 1;
  120.     //  vector<ll> answer(need, 0);
  121.     //  vector<int> aa(a.size());
  122.     //  vector<int> bb(b.size());
  123.  
  124.     //  for (int i = 0; i < a.size(); i++)
  125.     //      aa[i] = a[i] >> k;
  126.     //  for (int i = 0; i < b.size(); i++)
  127.     //      bb[i] = b[i] >> k;
  128.     //  vector<ll> c = multiply(aa, bb);
  129.     //  for (int i = 0; i < need; i++){
  130.     //      ll x = c[i] % mod;
  131.     //      answer[i] += x * (kkk - kk);
  132.     //  }
  133.  
  134.     //  for (int i = 0; i < a.size(); i++)
  135.     //      aa[i] = a[i] & (kk - 1);
  136.     //  for (int i = 0; i < b.size(); i++)
  137.     //      bb[i] = b[i] & (kk - 1);
  138.     //  c = multiply(aa, bb);
  139.     //  for (int i = 0; i < need; i++){
  140.     //      ll x = c[i] % mod;
  141.     //      answer[i] += x * (1 - kk);
  142.     //  }
  143.  
  144.     //  for (int i = 0; i < a.size(); i++)
  145.     //      aa[i] += a[i] >> k;
  146.     //  for (int i = 0; i < b.size(); i++)
  147.     //      bb[i] += b[i] >> k;
  148.     //  c = multiply(aa, bb);
  149.     //  for (int i = 0; i < need; i++){
  150.     //      answer[i] += c[i] % mod * kk;
  151.     //      answer[i] %= mod;
  152.     //      if (answer[i] < 0)
  153.     //          answer[i] += mod;
  154.     //  }
  155.  
  156.     //  vector<int> ans(need);
  157.     //  for (int i = 0; i < need; i++)
  158.     //      ans[i] = answer[i];
  159.     //  return ans;
  160.     // }
  161. };
  162.  
  163. int mod;
  164.  
  165. int power(ll a, int n){
  166.     ll res = 1;
  167.     while (n > 0){
  168.         if (n & 1)
  169.             res = res * a % mod;
  170.         a = a * a % mod;
  171.         n >>= 1;
  172.     }
  173.     return res;
  174. }
  175.  
  176.  
  177. int main(){
  178.     ios_base::sync_with_stdio(0);
  179.     cin.tie(0);
  180.     int n;
  181.     cin >> n >> mod;
  182.     vector<int> cnt(mod, 0);
  183.     for (int i = 1; i < mod; i++)
  184.         cnt[power(i, n)]++;
  185.     vector<ll> c = fft::multiply(cnt, cnt);
  186.     for (int i = mod; i < c.size(); i++)
  187.         c[i - mod] += c[i];
  188.     c.resize(mod);
  189.     ll answer = 0;
  190.     for (int i = 1; i < mod; i++){
  191.         int val = power(i, n) * 2 % mod;
  192.         answer += cnt[val];
  193.     }
  194.     for (int i = 0; i < mod; i++)
  195.         answer += cnt[i] * c[i];
  196.     assert(answer % 2 == 0);
  197.     cout << answer / 2 << endl;
  198.     return 0;
  199. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top