Slowest Decryption writeup

SlowestDecryption.md

Slowest Decryption

This is PPC problem.

For any i, v, x, we define cnt(i,v,x) as the number of P such that GCD(P)=v and P[i]=x. Then, the answer will be \sum_{i,v,x} cnt(i,v,x) * v * c[x] * i. Because cnt(i,v,x) = cnt(i',v,x), the answer can be written as \sum_{v,x} cnt(0,v,x) * v * c[x] * N*(N-1)/2.

To count cnt(0,v,x), we fix x. Then we check v from N-1 to 1 such that x % v = 0.

Because GCD(P)=v, all elements of P are multiple of v (including 0). The total number of P with multiples of v is ((N-1)//v + 1)^{N-1}. However, this contains some P with GCD(P)=2v, 3v, ..., so we subtract them from earlier calculations.

This algorithm looks working with O(N^2 log N) time complexity (log N is come from harmonic series of subtraction phase).

solve.cpp

#include <algorithm>
#include <boost/multiprecision/gmp.hpp>
#include <iostream>
#include <numeric>
#include <vector>

int c[20000] = {
    -271, 488,  -195, -33,  -103, -108, 221,  231,  428,  317,  -286, 129,
    -3,   445,  208,  -212, -240, -339, 280,  102,  -222, 42,   162,  135,
    -254, -33,  -435, 185,  113,  -390, -42,  -335, -327, -198, 132,  107,
    // ......
    -72,  -4,   -35,  -43,  22,   10,   40,   9,    22,   -23,  50,   7,
    -17,  -8,   20,   -25,  16,   4,    34,   12,   -2,   -128, 18,   0,
    -2,   0,    -3,   1,    22,   -2,   -4,   -25};

namespace mp = boost::multiprecision;
using Int = mp::mpz_int;

const Int MOD =
    Int("6936629689028940150218646671432409132718702325018122367524251114733771"
        "4372850256205482719088016822121023725770514726086328879208694006471882"
        "3544156277442635599506879146922114314913595038962794037965813659812250"
        "2306574965634652765248028923500895659393392857145770077965603073322931"
        "0882472880060831832351425517");

Int modpow(Int a, int b, Int md) {
  Int r = 1;
  while (b) {
    if (b & 1)
      r = r * a % md;
    a = a * a % md;
    b >>= 1;
  }
  return r;
}

Int cnt[20000];
std::vector<int> factors[20000];
int main() {
  int N = 20000;
  for (int v = N - 1; v > 0; v--) {
    int t = 0;
    while (t < N) {
      factors[t].push_back(v);
      t += v;
    }
  }
  Int total = 0;
  for (int v = 0; v < N; v++) {
    // for(int i=N-1; i>0; i--){
    for (int i : factors[v]) {
      int u = (N - 1) / i + 1;
      cnt[i] = modpow(u, N - 1, MOD);
      if (v == 0)
        cnt[i]--;
      int k = i + i;
      while (k <= factors[v][0]) {
        cnt[i] = (cnt[i] - cnt[k] + MOD) % MOD;
        k += i;
      }
      Int add = cnt[i] * c[v] * i % MOD;
      add *= (N - 1) * N / 2 % MOD;
      total += add;
      total %= MOD;
    }
    for (int i : factors[v]) {
      cnt[i] = 0;
    }
  }
  total %= MOD;
  total += MOD;
  total %= MOD;
  std::cout << total << std::endl;
  return 0;
}