AOJ 2353 Four Arithmetic Operations

この問題の既存の解説記事は中国剰余定理によるものが多かったので、それ以外の方法を示すのはいいかもなん。

AOJ 2353 Four Arithmetic Operations

問題概要

有理数列 がある。各項は以下のように定義される:

• 
• 

ただし は ＋、－、×、÷ のいずれかである。 を求めよ。

制約

• 
• は を満たす整数
• は 以上 未満の整数となる。

解法

原理的には多倍長整数を分母分子にもつ有理数演算を行っていけばよいのだが大変です。最終的な答えが整数になることから、素数 を法として計算してあげれば

• 分数も回避できる
• 途中結果も より小さい値に抑えられる

ということになります。求めたい値が 分の幅があるので、 としてそれより大きな値をとると途中結果の計算で long long int 型でもオーバーフローしてしまう。そこで mod の値が大きいときの mod 演算 に示した方法で問題を回避する。

別解として中国剰余定理を活用する方法も有効である。

#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 67280421310721LL;

inline long long mod(long long a, long long m) {
    return (a % m + m) % m;
}

inline long long mul(long long a, long long b, long long m) {
    a = mod(a, m); b = mod(b, m);
    if (b == 0) return 0;
    long long res = mul(mod(a + a, m), b>>1, m);
    if (b & 1) res = mod(res + a, m);
    return res;
}

inline long long inv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a/b;
        a = mod(a - mul(t, b, m), m); swap(a, b);
        u = mod(u - mul(t, v, m), m); swap(u, v);
    }
    return mod(u, m);
}

int main() {
  long long res = 0;
  int N; cin >> N;
  for (int i = 0; i < N; ++i) {
    long long o, y; cin >> o >> y;
    if (o == 1) res = mod(res + y, MOD);
    else if (o == 2) res = mod(res - y, MOD);
    else if (o == 3) res = mul(res, y, MOD);
    else res = mul(res, inv(y, MOD), MOD);
  }
  if (res <= 1LL<<31) cout << res << endl;
  else cout << res - MOD << endl;
}