提出 #47963804

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define FR first
#define SE second
#define int long long
using namespace std;
inline int read() {
  int x = 0; bool op = 0;
  char c = getchar();
  while(!isdigit(c))op |= (c == '-'), c = getchar();
  while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return op ? -x : x;
}
const int N = 1e6 + 10;
const int P = 998244353;
const int INF = 1e18;
int ksm(int x, int k) {
  int res = 1;
  for(int pw = x; k; (k & 1) ? res = 1ll * res * pw % P : 0, pw = 1ll * pw * pw % P, k >>= 1);
  return res;
}
int n, a, b, c, d;
int tot, pri[N], vis[N];
void sieve() {
  for(int i = 2; i < N; i++) {
    if(!vis[i])pri[++tot] = i;
    for(int j = 1; j <= tot && i * pri[j] < N; j++) {
      vis[i * pri[j]] = true;
      if(i % pri[j] == 0)break;
    }
  }
  return ;
}
int exgcd(int a, int b, int &x, int &y) {
  if(!b) {x = 1; y = 0; return a;}
  int res = exgcd(b, a % b, y, x); y -= (a / b) * x;
  return res;
}
int calc(int k, int b, int p) {
  int x, y, A = k, B = p, C = b;
  int g = exgcd(A, B, x, y);
  if(C % g)return -1;
  // assert(A * (C / g) * x + B * y * (C / g) == C);
  x = (x * (C / g) % (B / g) + (B / g)) % (B / g);
  if(k * x % p != b)cout << k << ' ' << b << ' ' << p << endl;
  assert(k * x % p == b);
  return x;
}
int dM, pM, rM;
void calcM() {
  vector<int> val(n);
  dM = pM = rM = 1;
  for(int i = 0; i < n; i++)val[i] = c + d * i;
  auto mul = [&](int x) {
    dM = dM * (x % d) % d;
    pM = pM * (x % P) % P;
    rM = (INF / x < rM ? INF + 1 : rM * x);
    // cout << "mul:" << x << ' ' << rM << endl;
    return ;
  };
  for(int i = 1; i <= tot; i++) {
    int st = calc(d, (pri[i] - c % pri[i]) % pri[i], pri[i]);
    if(!~st || st >= n)continue;
    int mx = 0;
    for(int j = st; j < n; j += pri[i]) {
      if(val[j] % pri[i] == 0) {
        int now = 0;
        while(val[j] % pri[i] == 0)
          now++, val[j] /= pri[i];
        mx = max(mx, now);
      }
    }
    while(mx--)mul(pri[i]);
  }
  for(int i = 0; i < n; i++)if(val[i] > 1)mul(val[i]);
  return ;
}
signed main() { 
  n = read(); a = read(); b = read(); c = read(); d = read();
  int g = __gcd(c, d), delta = a % g;
  if(b % g)return puts("-1"), 0;
  a /= g; b /= g; c /= g; d /= g;
  sieve();
  calcM();
  // printf("M:%lld %lld %lld\n", rM % P, dM, pM);
  // for(int i = 0; i < n; i++)assert(rM % (c + i * d) == 0);
  int v = a * d - b * c, ans = -1;
  if(rM != INF + 1)v = (v % rM + rM) % rM;
  for(int y = 0; y <= d; y++) {
    if(!y && v < 0)continue;
    int now = (dM * y % d + v % d + d) % d;
    if(!now) {ans = y; break;}
  }
  ans = ((pM * ans % P + v % P + P) % P * ksm(d, P - 2) * g % P + delta) % P;
  printf("%lld\n", ans);
  return 0;
}

提出情報

ジャッジ結果