結果

問題 No.2620 Sieve of Coins
ユーザー SSRS
提出日時 2024-01-26 23:25:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 4,816 bytes
コンパイル時間 2,857 ms
コンパイル使用メモリ 221,812 KB
最終ジャッジ日時 2025-02-18 23:47:19
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 MLE * 1 -- * 1
other -- * 53
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
long long modpow(long long a, long long b){
  long long ans = 1;
  while (b > 0){
    if (b % 2 == 1){
      ans *= a;
      ans %= MOD;
    }
    a *= a;
    a %= MOD;
    b /= 2;
  }
  return ans;
}
long long modinv(long long a){
  return modpow(a, MOD - 2);
}
vector<pair<int, pair<int, int>>> quotient_ranges(int N){
    vector<pair<int, pair<int, int>>> ans;
    for (int i = 1; i * i <= N; i++){
        ans.push_back(make_pair(N / i, make_pair(i, i)));
    }
    for (int i = N / ((int) sqrt(N) + 1); i >= 1; i--){
        ans.push_back(make_pair(i, make_pair(N / (i + 1) + 1, N / i)));
    }
    return ans;
}
long long sqrt_floor(long long N){
  long long tv = 0, fv = 1100000000;
  while (fv - tv > 1){
    long long mid = (tv + fv) / 2;
    if (mid * mid <= N){
      tv = mid;
    } else {
      fv = mid;
    }
  }
  return tv;
}
bool is_square_number(long long N){
  long long x = sqrt_floor(N);
  return x * x == N;
}
long long cbrt_floor(long long N){
  long long tv = 0, fv = 1100000;
  while (fv - tv > 1){
    long long mid = (tv + fv) / 2;
    if (mid * mid * mid <= N){
      tv = mid;
    } else {
      fv = mid;
    }
  }
  return tv;
}
long long cbrt_ceil(long long N){
  return cbrt_floor(N - 1) + 1;
}
pair<vector<long long>, vector<long long>> dirichlet_sum_division(long long N, int K, int L, vector<long long> a, vector<long long> c, vector<long 
    long> A, vector<long long> C){
  vector<long long> b = c;
  long long INV_a1 = modinv(a[1]);
  for (int i = 1; i <= K; i++){
    b[i] *= INV_a1;
    b[i] %= MOD;
    for (int j = i * 2; j <= K; j += i){
      b[j] += MOD - a[j / i] * b[i] % MOD;
      b[j] %= MOD;
    }
  }
  vector<long long> asum(K + 1), bsum(K + 1);
  asum[0] = 0;
  bsum[0] = 0;
  for (int i = 1; i <= K; i++){
    asum[i] = (asum[i - 1] + a[i]) % MOD;
    bsum[i] = (bsum[i - 1] + b[i]) % MOD;
  }
  vector<long long> B(L + 1, 0);
  for (int i = L; i >= 1; i--){
    B[i] = C[i];
    long long M = sqrt_floor(N / i);
    for (int j = 2; j <= M; j++){
      if (N / i / j <= K){
        B[i] += MOD - a[j] * bsum[N / i / j] % MOD;
        B[i] %= MOD;
      } else {
        B[i] += MOD - a[j] * B[i * j] % MOD;
        B[i] %= MOD;
      }
    }
    long long AM;
    if (M <= K){
      AM = asum[M];
    } else {
      AM = A[N / M];
    }
    for (int j = 1; j <= M; j++){
      if (N / i / j <= K){
        B[i] += MOD - b[j] * asum[N / i / j] % MOD;
      } else {
        B[i] += MOD - b[j] * A[i * j] % MOD;
      }
      B[i] += b[j] * AM;
      B[i] %= MOD;
    }
    B[i] *= INV_a1;
    B[i] %= MOD;
  }
  return make_pair(b, B);
}
long long solve(long long N){
  if (N == 0){
    return 0;
  }
  vector<long long> small, large;
  int L = cbrt_ceil(N);
  int K = (N + L - 1) / L;
  vector<long long> a(K + 1, 0), c(K + 1, 0);
  vector<long long> A(L + 1, 0), C(L + 1, 0);
  for (int i = 1; i <= K; i++){
    c[i] = 1;
  }
  for (int i : {1, 2, 3, 6}){
    for (int j = 1; j * j * i <= K; j++){
      a[j * j * i]++;
    }
  }
  for (int i = 1; i <= L; i++){
    for (int j : {1, 2, 3, 6}){
      A[i] += sqrt_floor(N / i / j);
    }
    C[i] = N / i;
  }
  vector<long long> b, B;
  tie(b, B) = dirichlet_sum_division(N, K, L, a, c, A, C);
  return B[1];
};
int main(){
  long long L;
  int N;
  cin >> L >> N;
  vector<long long> A(N);
  for (int i = 0; i < N; i++){
    cin >> A[i];
  }
  vector<long long> P2 = {1};
  while (P2.back() * 2 <= L){
    long long x = P2.back() * 2;
    P2.push_back(x);
  }
  vector<long long> P3 = {1};
  while (P3.back() * 3 <= L){
    long long x = P3.back() * 3;
    P3.push_back(x);
  }
  int C2 = P2.size();
  int C3 = P3.size();
  vector<vector<long long>> V(C2, vector<long long>(C3));
  for (int i = 0; i < C2; i++){
    for (int j = 0; j < C3; j++){
      if (L / P2[i] < P3[j]){
        V[i][j] = L + 1;
      } else {
        V[i][j] = P2[i] * P3[j];
      }
    }
  }
  map<long long, pair<int, int>> mp;
  for (int i = 0; i < C2; i++){
    for (int j = 0; j < C3; j++){
      if (V[i][j] <= L){
        mp[V[i][j]] = make_pair(i, j);
      }
    }
  }
  vector<vector<bool>> head(C2, vector<bool>(C3, false));
  for (int i = 0; i < N; i++){
    pair<int, int> P = mp[A[i]];
    head[P.first][P.second] = true;
  }
  for (int i = 0; i < C2; i++){
    for (int j = 0; j < C3; j++){
      if (head[i][j]){
        for (int k = i; k < C2; k++){
          for (int l = j; l < C3; l++){
            if (!(k == i && l == j)){
              head[k][l] = !head[k][l];
            }
          }
        }
      }
    }
  }
  long long ans = 0;
  for (int i = 0; i < C2; i++){
    for (int j = 0; j < C3; j++){
      if (head[i][j] && V[i][j] <= L){
        ans += solve(L / V[i][j]);
      }
    }
  }
  cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0