Algoogle

Algorithm for Programming Contest

AOJ 2353 Four Arithmetic Operations

Category: AOJ Tag: math, modulo

Four Arithmetic Operations

問題概要


解法


計算結果の絶対値は2^31に収まるけど, 途中経過が余裕でオーバーしてくるので
適当にmodとってやる
->掛け算でオーバーフローするのでだめ
(BigInteger使えるならそれで大丈夫なはず)

中国式剰余定理なら素数m,nについて
y ≡ a (mod m), y ≡ b (mod n) のとき,
x ≡ y (mod mn)
となるxが一意に定まる.
このことからm, nを適当な大きさでとればオーバーフローなくxを求められる.

コード


(2353.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

long long extgcd(long long a, long long b, long long &x, long long &y) {
    long long g = a; x = 1; y = 0;
    if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
    return g; // 1なら解あり
}

long long mod_inverse(long long a, long long m){
    long long x, y;
    if(extgcd(a, m, x, y) != 1) return 0; // unsolvable
    return (m + x % m) % m;
}

const ll m = 999979, n = 999983;

void calc(ll &mx, ll &nx, int o, int y){
    switch(o){
    case 1:
        mx = (mx + y) % m;
        nx = (nx + y) % n;
        break;
    case 2:
        mx = (mx - y + m) % m;
        nx = (nx - y + n) % n;
        break;
    case 3:
        mx = mx * y % m;
        nx = nx * y % n;
        break;
    case 4:
        mx = mx * mod_inverse(y,m) % m;
        nx = nx * mod_inverse(y,n) % n;
        break;
    }
}

int main(){
    int N;
    ll mx = 0, nx = 0;
    cin >> N;
    while(N--){
        ll o, y;
        cin >> o >> y;
        calc(mx,nx,o,y);
    }
    ll s, t;
    extgcd(m,n,s,t);
    ll x = (m * s * nx + n * t * mx) % (m * n);
    if(x >= 1LL<<31) x -= m * n;
    cout << x << endl;
    return 0;
}

Comments