Submission #1779261

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;

struct NumberTheoreticTransform
{
  int64 mod;
  int64 primitiveroot;

  NumberTheoreticTransform(int64 mod, int64 root) : mod(mod), primitiveroot(root) {}

  inline int64 mod_pow(int64 x, int64 n)
  {
    int64 ret = 1;
    while(n > 0) {
      if(n & 1) ret = mul(ret, x);
      x = mul(x, x);
      n >>= 1;
    }
    return ret;
  }

  inline int64 inverse(int64 x)
  {
    return (mod_pow(x, mod - 2));
  }

  inline int64 add(int64 x, int64 y)
  {
    x += y;
    if(x >= mod) x -= mod;
    return (x);
  }

  inline int64 mul(__int128 a, int64 b)
  {
    return (a * b % mod);
  }

  void DiscreteFourierTransform(vector< int64 > &F, bool rev)
  {
    const int N = (int) F.size();
    for(int i = 0, j = 1; j + 1 < N; j++) {
      for(int k = N >> 1; k > (i ^= k); k >>= 1);
      if(i > j) swap(F[i], F[j]);
    }
    int64 w, wn, s, t;
    for(int i = 1; i < N; i <<= 1) {
      w = mod_pow(primitiveroot, (mod - 1) / (i * 2));
      if(rev) w = inverse(w);
      for(int k = 0; k < i; k++) {
        wn = mod_pow(w, k);
        for(int j = 0; j < N; j += i * 2) {
          s = F[j + k], t = mul(F[j + k + i], wn);
          F[j + k] = add(s, t), F[j + k + i] = add(s, mod - t);
        }
      }
    }
    if(rev) {
      int64 temp = inverse(N);
      for(int i = 0; i < N; i++) F[i] = mul(F[i], temp);
    }
  }

  vector< int64 > Multiply(const vector< int > &A, const vector< int > &B)
  {
    int sz = 1;
    while(sz < A.size() + B.size() - 1) sz <<= 1;
    vector< int64 > F(sz), G(sz);
    for(int i = 0; i < A.size(); i++) F[i] = A[i];
    for(int i = 0; i < B.size(); i++) G[i] = B[i];
    DiscreteFourierTransform(F, false);
    DiscreteFourierTransform(G, false);
    for(int i = 0; i < sz; i++) F[i] = mul(F[i], G[i]);
    DiscreteFourierTransform(F, true);
    F.resize(A.size() + B.size() - 1);
    return (F);
  }
};

int main()
{
  int N;
  scanf("%d", &N);
  vector< int > A(N + 1), B(N + 1);
  for(int i = 0; i < N; i++) scanf("%d %d", &A[i + 1], &B[i + 1]);
  NumberTheoreticTransform ntt(4179340454199820289, 3);
  auto C = ntt.Multiply(A, B);
  for(int i = 1; i <= 2 * N; i++) printf("%lld\n", C[i]);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:86:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
                  ^
./Main.cpp:88:66: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   for(int i = 0; i < N; i++) scanf("%d %d", &A[i + 1], &B[i + 1]);
                                                                  ^

Judge Result