結果

問題 No.3365 Prefix and Suffix X
コンテスト
ユーザー tnakao0123
提出日時 2025-11-20 17:08:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,133 bytes
コンパイル時間 1,023 ms
コンパイル使用メモリ 70,880 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-11-20 17:08:23
合計ジャッジ時間 11,433 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 WA * 25
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:146:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  146 |   scanf("%d", &tn);
      |   ~~~~~^~~~~~~~~~~
main.cpp:150:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  150 |     scanf("%s%d", sx, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

/* -*- coding: utf-8 -*-
 *
 * 3365.cc:  No.3365 Prefix and Suffix X - yukicoder
 */

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

/* constant */

const int MAX_N = 3;
const int MAX_L = 18;
const int MAX_P = 32000;

/* typedef */

using ll = long long;
using vb = vector<bool>;
using vi = vector<int>;
using pii = pair<int,int>;
using vpii = vector<pii>;

struct MI {
  static int MOD;
  int v;
  MI(): v() {}
  MI(int _v): v(_v % MOD) { if (v < 0) v += MOD; }
  MI(long long _v): v(_v % MOD) { if (v < 0) v += MOD; }

  explicit operator int() const { return v; }
  
  MI operator+(const MI m) const { return MI(v + m.v); }
  MI operator-(const MI m) const { return MI(v + MOD - m.v); }
  MI operator-() const { return MI(MOD - v); }
  MI operator*(const MI m) const { return MI((long long)v * m.v); }

  MI &operator+=(const MI m) { return (*this = *this + m); }
  MI &operator-=(const MI m) { return (*this = *this - m); }
  MI &operator*=(const MI m) { return (*this = *this * m); }

  bool operator==(const MI m) const { return v == m.v; }
  bool operator!=(const MI m) const { return v != m.v; }

  MI pow(int n) const {  // a^n % MOD
    MI pm = 1, a = *this;
    while (n > 0) {
      if (n & 1) pm *= a;
      a *= a;
      n >>= 1;
    }
    return pm;
  }

  MI inv() const { return pow(MOD - 2); }
  MI operator/(const MI m) const { return *this * m.inv(); }
  MI &operator/=(const MI m) { return (*this = *this / m); }
};
int MI::MOD;
using mi = MI;

/* global variables */

vb primes;
vi pnums;
char sx[MAX_N + 4], sy[MAX_L + 4], sz[MAX_L + 4];
mi ts[MAX_L + 1];

/* subroutines */

int gen_primes(int maxp) {
  primes.assign(maxp + 1, true);
  primes[0] = primes[1] = false;

  int p;
  for (p = 2; p * p <= maxp; p++)
    if (primes[p]) {
      pnums.push_back(p);
      for (int q = p * p; q <= maxp; q += p) primes[q] = false;
    }
  for (; p <= maxp; p++)
    if (primes[p]) pnums.push_back(p);
  return (int)pnums.size();
}

vpii prime_decomp(int n) {
  vpii pds;

  for (auto pi: pnums) {
    if (pi * pi > n) {
      if (n > 1) pds.push_back(pii(n, 1));
      break;
    }

    if (n % pi == 0) {
      int fi = 0;
      while (n % pi == 0) n /= pi, fi++;
      pds.push_back(pii(pi, fi));
    }
  }
  return pds;
}

int powi(int a, int b) {
  int p = 1;
  while (b > 0) {
    if (b & 1) p *= a;
    a *= a;
    b >>= 1;
  }
  return p;
}

int phi(int m) {
  auto pds = prime_decomp(m);
  int ph = 1;
  for (auto [p, d]: pds)
    ph *= (p - 1) * powi(p, d - 1);
  return ph;
}

mi s2i(int n, char s[]) {
  mi sum = 0;
  for (int i = 0; i < n; i++) sum = sum * 10 + (s[i] - '0');
  return sum;
}

int i2s(int n, char s[]) {
  int l = 0;
  while (n > 0) s[l++] = '0' + (n % 10), n /= 10;
  s[l] = '\0';
  reverse(s, s + l);
  return l;
}

/* main */

int main() {
  gen_primes(MAX_P);
  
  int tn;
  scanf("%d", &tn);

  while (tn--) {
    int m;
    scanf("%s%d", sx, &m);
    int n = strlen(sx);
    MI::MOD = m;

    bool f = false;
    for (int i = n; i >= 0; i--) {
      strcpy(sy, sx); strcpy(sy + n - i, sx);
      if (! strncmp(sy, sx, n)) {
	if (s2i(n * 2 - i, sy) == 0) {
	  f = true;
	  break;
	}
      }
    }
    if (f) { puts(sy); continue; }

    if (m % 2 == 0 || m % 5 == 0) { puts("-1"); continue; }
	
    ts[0] = 1;
    for (int i = 0; i < MAX_L; i++) ts[i + 1] = ts[i] * 10;

    // y = x*t[n+zl]+z*t[n]+x = x*(t[n+zl]+1)+z*t[n] == 0
    // -> z*t[n] == -x*(t[n+zl]+1)
    // -> z == -x*(t[n+zl]+1)*t[n]^(-1)

    int phm = phi(m);
    mi x = s2i(n, sx), invtn = ts[n].pow(phm - 1);
    for (int zl = 1; zl + n * 2 <= MAX_L; zl++) {
      mi z = -x * (ts[n + zl] + 1) * invtn;
      int l = i2s((int)z, sz);
      //printf(" zl=%d, l=%d, sz=%s\n", zl, l, sz);
      if (l <= zl) {
	fill(sy, sy + (zl + n * 2), '0');
	copy(sx, sx + n, sy);
	copy(sx, sx + n, sy + (n + zl));
	copy(sz, sz + l, sy + (n + zl - l));
	sy[zl + n * 2] = '\0';
	
	int r = (int)s2i(zl + n * 2, sy);
	//printf(" %s == %d\n", sy, r);
	if (r == 0) {
	  f = true;
	  break;
	}
      }
    }

    if (f) puts(sy);
    else puts("-1");
  }

  return 0;
}
0